解题 (HGOI 2019.2.16 T3)

2019-02-16 16:19:13


题目大意

数据范围

n<=300,m<=1000

解法

小小的一道DP打错了orz

一开始还以为是一道贪心题,后然发现不行的说。。

80 90
10 90
90 10

这样贪心的话显然是要6个月的,但是,2、3合并的话,只用5个月

dp[i][j]=k,表示第i月,完成了j个任务,本月剩余k元

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,a[310],b[310];
int dp[310][310];
int main()
{
    memset(dp,-1,sizeof(dp));
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i],&b[i]);
    dp[1][0]=m;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=n;j++)
        {
            if(dp[i][j]<0) break;
            int res1=dp[i][j],res2=m;
            dp[i+1][j]=max(dp[i+1][j],m);
            for(int k=j+1;k<=n;k++)
            {
                if(res1-a[k]<0 || res2-b[k]<0) break;
                res1-=a[k],res2-=b[k];
                dp[i+1][k]=max(dp[i+1][k],res2);
            }
        }
    int ans;
    for(int i=1;i<=2*n;i++)
        if(dp[i][n]!=-1) {ans=i;break;}
    printf("%d",ans+1);
    return 0;
}