题解 P2876 【[USACO07JAN]解决问题Problem Solving】
whyl
2019-10-26 07:35:19
这道题一眼一看感觉像是一个贪心
结果将贪心算法写上去之后WA掉了
只拿到了30分的部分分
很尴尬
于是考虑了动态规划
定义状态为f[i][j]为到i题下个月要花费多少钱
方程 f[i][sum2[i]-sum2[j-1]]=min(f[j-1][k]+1,f[i][sum2[i]-sum2[j-1]]);
if(j==0) f[i][0]=min(f[i][0],mi+1);
进行转移即可
附代码
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;
char p=getchar();
while(!isdigit(p)){
if(p=='-') f=-1;
p=getchar();
}
while(isdigit(p)) x=(x<<3)+(x<<1)+(p^48),p=getchar();
return x*f;
}
#define int long long
const int maxn=305;
int m,p,v1[maxn],v2[maxn],f[maxn][1005],sum1[maxn],mi;
int sum2[maxn];
signed main(){
freopen("data.in","r",stdin);
freopen("man.txt","w",stdout);
m=read();p=read();
for(int i=1;i<=p;i++) v1[i]=read(),v2[i]=read();
for(int i=1;i<=p;i++) sum1[i]=sum1[i-1]+v1[i];
for(int i=1;i<=p;i++) sum2[i]=sum2[i-1]+v2[i];
for(int i=0;i<=p;i++) for(int j=0;j<=m;j++) f[i][j]=1e7;
f[0][0]=0;
for(int i=1;i<=p;i++){
for(int j=i;j>=1;j--){
if(sum2[i]-sum2[j-1]>m) break;
mi=1e7;
for(int k=0;k+sum1[i]-sum1[j-1]<=m;k++){
f[i][sum2[i]-sum2[j-1]]=min(f[j-1][k]+1,f[i][sum2[i]-sum2[j-1]]);
mi=min(mi,f[i][sum2[i]-sum2[j-1]]);
}
f[i][0]=min(f[i][0],mi+1);
}
}
int ans=1e7;
for(int i=0;i<=m;i++) ans=min(ans,f[p][i]);
cout<<ans+2<<endl;
return 0;
}
```