【DP】书的复制

【思路】

（区间）DP

F[I][J]表示前i本书分给j个人用的最短时间

由于每一次j的状态由比j小的状态得出，所以要先枚举j，然后枚举i，接着枚举上一次抄书的人是谁

我觉得，难点在于输出

具体见代码

压行压到手抽筋

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

inline int read(){

	char chr=getchar();int f=1,ans=0;

	while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}

	while(isdigit(chr))  {ans=ans*10;ans+=chr-'0';chr=getchar();}

	return ans*f;

}

int a[505],f[505][505],n=read(),m=read(),s=0,&ans=f[n][m],num=0,w=n,pre[505],x;

void output(int x){

	if(x>0) output(pre[x]-1); else return; if(pre[x]<=0) return;printf("%d %d\n",pre[x],x);}//这里递归输出

int main(){

	memset(f,127/2,sizeof(f));memset(pre,0,sizeof(pre));f[0][1]=0;

	if(!n&&!m) return 0;//坑点！！！

	for(int i=1;i<=n;i++)

		a[i]=read(),f[i][1]=f[i-1][1]+a[i];//前i本书都交给第一个人抄(即a[i]的前缀和)

	for(int j=2;j<=m;j++)

		for(int i=j;i<=n;i++)

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

				int x=max(f[k-1][j-1],f[i][1]-f[k-1][1]);//取两者最长的抄书时间

				if(f[i][j]>x) f[i][j]=x;//取最小值

			}

	for(int i=n;i>=1;i--){//这里贪心，因为后面的人抄尽量多，前面少，所以倒过来枚举

		s+=a[i];

		if(s>ans) s=a[i],pre[w]=i+1,w=i;//pre[w]记录这个人抄书的开始位置

	}

	printf("%d %d\n",1,w);//第一组特判

	output(n);//递归输出

	return 0;

}

打完收工

hia_hiahia~

巴特西

【DP】书的复制

【思路】

我觉得，难点在于输出

打完收工

最新文章

热门文章