[文章目录]
Description
过去的日子里,农夫John的牛没有任何题目. 可是现在他们有题目,有很多的题目. 精确地说,他们有P (1 <= P <= 300) 道题目要做. 他们还离开了农场并且象普通人一样找到了工作. 他们的月薪是M (1 <= M <= 1000) 元. 他们的题目是一流的难题,所以他们得找帮手.帮手们不是免费的,但是他们能保证在一个月内作出任何题目.每做一道题需要两比付款, 第一笔A_i(1 <= A_i <= M) 元在做题的那一个月初支付, 第二笔B_i元(1 <= B_i <= M)在做完后的下一个月初支付. 每一个月牛们用上一个月挣的钱来付款. 牛没有任何存款意识, 所以每个月的节余都回拿用去买糖吃掉了. 因为题目是相互关连的,它们必须按大概顺序解出. 比如,题目3必须在解题目4 之前或同一个月解出. 找出牛们做完所有题目并支付完所有款项的最短月数.
DP
本来写的二维背包，发现复杂度不对。
发现剩下的钱其实是一些固定的值，就是当前往前的一段区间的付款。那么可以改一下dp的状态，dp[i][j]表示[i,j]在最后一个月做的最短时间。转移O(n)，时间复杂度O(n^3)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,a[310],b[310];
int dp[310][310];
int main()
{
scanf("%d%d",&n,&m); int x,y;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&x,&y);
a[i]=a[i-1]+x; b[i]=b[i-1]+y;
}
memset(dp,0x3f,sizeof dp);
for(int i=1;i<=m;++i)
{
if(a[i]<=n&&b[i]<=n) dp[i][1]=3;
for(int j=2;j<=i;++j) if(b[i]-b[j-1]<=n&&a[i]-a[j-1]<=n)
{
for(int k=1;k<=j-1;++k)
{
if(a[i]-a[j-1]+b[j-1]-b[k-1]<=n) dp[i][j]=min(dp[i][j],dp[j-1][k]+1);
else dp[i][j]=min(dp[i][j],dp[j-1][k]+2);
}
}
}
int ans=0x3f3f3f3f;
for(int i=1;i<=m;++i) ans=min(ans,dp[m][i]);
printf("%d",ans);
return 0;
}