BZOJ 1700 [Usaco2007 Jan]Problem Solving 解题（单调DP）

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1700

【题目大意】

　　共有p道题目要做，每个月收入只有n元，用于付钱做题之外的部分都会吃掉，
　　做题要按顺序来解决，对于一道题，在这个月需要付预做费用，下个月开始的时候还要付完成费用，
　　上一个月才会发上个月的工资，问最少几个月能做完这些题目

【题解】

　　dp[j][i]表示当前最后一个月做j到i的题目用的最小月份，
　　我们发现如果当前月能结算上个月的完成费用和这个月的预付费用，则转移时答案加一，
　　否则转移时答案加2，顺序dp即可。

【代码】

#include <cstdio>

#include <algorithm>

#include <cstring>

using namespace std;

int n,p,a[1010],b[1010],as[1010],bs[1010],dp[310][310];

int main(){

    while(~scanf("%d%d",&n,&p)){

        for(int i=1;i<=p;i++){

            scanf("%d%d",&a[i],&b[i]);

            as[i]=as[i-1]+a[i];

            bs[i]=bs[i-1]+b[i];

        }memset(dp,0x3f,sizeof(dp));

        for(int i=1;i<=p;i++){

            if(as[i]<=n&bs[i]<=n)dp[1][i]=1;

            else break;

        }int ans=0x3f3f3f3f3f;

        for(int i=1;i<=p;i++){

            for(int j=1;j<=i;j++){

                for(int k=1;k<j;k++){

                    if(as[i]-as[j-1]<=n&&bs[i]-bs[j-1]<=n)

                        dp[j][i]=min(dp[j][i],dp[k][j-1]+2);

                    if(as[i]-as[j-1]+bs[j-1]-bs[k-1]<=n&&bs[i]-bs[j-1]<=n)

                        dp[j][i]=min(dp[j][i],dp[k][j-1]+1);

                }if(i==p)ans=min(ans,dp[j][i]);

            }

        }printf("%d\n",ans+2);

    }return 0;

}

巴特西

BZOJ 1700 [Usaco2007 Jan]Problem Solving 解题（单调DP）

最新文章

热门文章