luoguP1281 书的复制

链接

https://www.luogu.org/problemnew/show/P1281

思路

简单dp，输出方案。

很明显dp记录路径对不对？

恭喜你死了。

求出dp值，倒叙贪心取最长

错误

好久之前咕咕的题目

下载数据才看出来不能记录路径

代码

#include <bits/stdc++.h>

using namespace std;

const int N=507;

const int inf=0x3f3f3f3f;

int read() {

	int x=0,f=1;char s=getchar();

	for(;s>'9'||s<'0';s=getchar()) if(s=='0') f=-1;

	for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

	return x*f;

}

int n,K,sum[N],f[N][N],stak[N],top;

vector<pair<int,int> > a;

int main() {

	n=read(),K=read();

	for(int i=1;i<=n;++i) sum[i]=sum[i-1]+read();

	memset(f,0x3f,sizeof(f));

	f[0][0]=0;

	for(int k=1;k<=K;++k)

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

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

				f[i][k]=min(f[i][k],max(f[j-1][k-1],sum[i]-sum[j-1]));

	int r=n,tot=0;

	for(int i=n;i>=1;--i) {

		tot+=sum[i]-sum[i-1];

		if(tot>f[n][K]) {

			a.push_back(make_pair(i+1,r));

			tot=sum[i]-sum[i-1];

			r=i;

		}

	}

	if(tot) a.push_back(make_pair(1,r));

	for(vector<pair<int,int> >::iterator it=a.end()-1;it!=a.begin()-1;it--)

		printf("%d %d\n",it->first,it->second);

	return 0;

}

巴特西

luoguP1281 书的复制 DP，贪心

luoguP1281 书的复制

链接

思路

错误

代码

最新文章

热门文章