题解 P2876 【[USACO07JAN]解决问题Problem Solving】

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);

进行转移即可

附代码

#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;
}