poj 2228 Naptime（DP的后效性处理）

$ Naptime $

描述

Goneril是一只睡眠不足的母牛。她的一天被划分为N（3 <= N <= 3,830）相等的时间段，但她只能在床上花费B（2 <= B <N）不一定是连续的时期。由于她的牛激素水平，每个时期都有自己的效用U_i（0 <= U_i <= 200,000），这是在此期间从睡眠中获得的休息量。这些效用值是固定的，与Goneril选择做的无关，包括她决定在床上时。

在她的闹钟的帮助下，她可以准确选择在床上度过的时间段和花费更多关键项目的时间，例如写论文或看棒球。但是，她只能在一段时间内进入或下床。

她想选择她的睡眠时间，以最大限度地提高她在睡觉期间的效用总和。不幸的是，每次她爬到床上，她都必须在第一段时间内入睡，并且从那个时期起就没有睡眠效用。

周期环绕一圈; 如果Goneril在床上花费N和1期，那么她确实会在1期内获得

睡眠效用.Goneril可以达到的最大睡眠效用是多少？

输入

*第1行：两个以空格分隔的整数：N和B

*第2..N + 1行：第i + 1行包含一个0到200,000之间的整数U_i

输出

这一天分为5个时段，按顺序为实用工具2,0,3,1,4。Goneril必须选择3个时期。

样本输入

5 3

2

0

3

1

4

样本输出

$ solution: $

这道题用了取消环形后效性的第二种方法：强制两次线性DP。为什么可以用两次DP来取消环形后效性呢？我们发现这道题原本就是一道线性DP，只是现在它变成了一个环。于是我们考虑如果我们从某个节点拆开这个环会有什么情况我们算不到（现在我们以断开一号节点与最后一个节点举例），于是在这个环上得出的答案，一定可以分为两种情况，一种是它睡的这几个小时里不会连续包括最后一个小时和第一个小时，第二种就是这几个小时是有两天共同平凑出来的（就是最后一个小时和第一个小时都在睡觉）。于是我们自然想到能不能分开求两种情况，第一种直接线性DP就行了，而第二种我们琢磨一下就能发现这种情况一定要选第一个小时睡觉！然后就行了。

$ code: $

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define inf 0x7fffffff

#define rg register int

using namespace std;

int n,m,ans;

int a[4005];

int f[4005][2];

inline int qr(){

	register char ch; register bool sign=0; rg res=0;

	while(!isdigit(ch=getchar())) if(ch=='-')sign=1;

	while(isdigit(ch)) res=res*10+(ch^48),ch=getchar();

	return sign?-res:res;

}

int main(){

	//freopen(".in","r",stdin);

	//freopen(".out","w",stdout);

	n=qr(); m=qr();

	for(rg i=1;i<=n;++i) a[i]=qr();

	for(rg i=0;i<=n;++i)

		f[i][0]=f[i][1]=-1e9;

	f[0][0]=0;

	for(rg i=1;i<=n;++i){

		rg x=min(i,m);

		for(rg j=x;j>=0;--j){

			f[j][0]=max(f[j][0],f[j][1]);

			if(j)f[j][1]=max(f[j-1][0],f[j-1][1]+a[i]);

		}

	}ans=max(f[m][0],f[m][1]);

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

		f[i][0]=f[i][1]=-1e9;

	f[1][1]=a[1];

	for(rg i=2;i<=n;++i){

		rg x=min(i,m);

		for(rg j=x;j>=0;--j){

			f[j][0]=max(f[j][0],f[j][1]);

			if(j)f[j][1]=max(f[j-1][0],f[j-1][1]+a[i]);

		}

	}ans=max(ans,f[m][1]);

	printf("%d\n",ans);

	return 0;

}

巴特西