#|【2018/09/15测试T2】【SOJ 1805】切木板
【题目】 题目描述：
有一个 
文章图片
的矩形木板。你需要把这个木板切成 
文章图片
的小方块，也就是竖着切 
文章图片
刀、横着切 
文章图片
刀。横着切第 
文章图片
个位置的权值为 
文章图片
，竖着切第 
文章图片
个位置的权值为 
文章图片
。切某一刀时的费用为切这一刀的权值乘上切过的块数。
请你安排切的顺序使得所有费用之和最小。
输入格式：
第一行两个数 
文章图片
，
文章图片
。
接下来一行
文章图片
个整数 
文章图片
，
文章图片
，…，
文章图片
。
接下来一行
文章图片
个整数 
文章图片
，
文章图片
，…，
文章图片
。
输出格式：
输出一个数，表示最小的费用之和 
文章图片
文章图片
。
样例数据：
输入
6 4 2 1 3 1 4 4 1 2
输出
42
备注：
【数据规模与约定】
对于 30% 的数据，
文章图片
≤ 10 。
对于 60% 的数据，
文章图片
≤ 500 。
对于 100% 的数据， 2 ≤
文章图片
≤
文章图片
；0 ≤
文章图片
≤
文章图片
。
【提醒】
建议本题加读入优化。
【分析】 就是贪心+模拟吧，应该不是很难
【代码】
#include
#include
#include
#include
#define N 1000005
#define mod 1000000007
using namespace std;
int Read()
{
int x=0;
char c=getchar();
while(!isdigit(c))
c=getchar();
while(isdigit(c))
{
x=(x<<1)+(x<<3)+(c^'0');
c=getchar();
}
return x;
}
int x[N],y[N];
bool cmp(int a,int b){return a>b;
}
int main()
{
// freopen("cutboard.in","r",stdin);
// freopen("cutboard.out","w",stdout);
int m,n,i,j,ans=0;
m=Read(),n=Read();
//scanf("%d%d",&m,&n);
for(i=1;
iy[j])ans=(ans+1ll*x[i++]*j)%mod;
if(x[i]<=y[j])ans=(ans+1ll*y[j++]*i)%mod;
}
while(i 【#|【2018/09/15测试T2】【SOJ 1805】切木板】
推荐阅读
- 宽容谁
- 我要做大厨
- 2018-02-06第三天|2018-02-06第三天 不能再了，反思到位就差改变
- 增长黑客的海盗法则
- 画画吗（）
- 2018年11月19日|2018年11月19日 星期一 亲子日记第144篇
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文