自动搬运

查看原文

来自洛谷，原作者为

	whyl 弱者就是会被欺负呀

搬运于2025-08-24 21:42:34，当前版本为作者最后更新于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;
}