我的思路是:对每一个i,枚举j,考虑是否可以在i,j间移动泥土。但是这种算法好像不是正解,Wrong了五个点,求大佬指点为什么不行
#include <iostream>
using namespace std;
const int maxn = 110;
int a[maxn],b[maxn],n,x,y,z,ans;
int main()
{
cin>>n>>x>>y>>z;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
a[i] -= b[i];
//若a[i]为正,则a[i]--消耗y
//若a[i]为负,则a[i]++消耗x
}
for(int i=1;i<=n;i++)
{
if(a[i]>0)
{
for(int j=i+1;j<=n;j++)//考虑每一个j,若a[j]与a[i]异号,则可以移动泥土
{
if(z*(j-i)>(x+y)||a[i]==0)//如果移动泥土不如直接+/-划算,或者已经达到目标状态,跳出循环
break;
if(a[j]<0)
{
int num = min(a[i],-a[j]);//可移动泥土数量
a[j] += num;
a[i] -= num;
ans += num*z*(j-i);
}
}
ans += a[i] * y;//剩下的泥土全都要移除
}
else if(a[i]<0)
{
for(int j=i+1;j<=n;j++)//考虑每一个j,若a[j]与a[i]异号,则可以移动泥土
{
if(z*(j-i)>(x+y)||a[i]==0)//如果移动泥土不如直接+/-划算,或者已经达到目标状态,跳出循环
break;
if(a[j]>0)
{
int num = min(-a[i],a[j]);//可移动泥土数量
a[j] -= num;
a[i] += num;
ans += num*z*(j-i);
}
}
ans += (-a[i]) * x;//剩下的泥土全都要加上
}
}
cout<<ans;
return 0;
}
样例附上:输入
20 12 11 1
10 3
1 3
4 8
6 10
3 3
9 10
8 4
7 2
3 10
4 2
10 5
8 9
5 6
1 4
7 2
1 7
4 3
1 7
2 6
6 5
输出
157