本文主要是介绍POJ 2228 Naptime 环状DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一个环，分成 N 个区间，每个区间有个权值，你可以选择 B 个不同的区间，这些区间可以连续也可以不连续。
那么如何使得选中的区间中的权值之和最大。有个限制条件，被选中的任何连续区间，第一个区间的权值是不算的。
比如你选中编号为 k, k + 1, k + 2 的这 3 个区间时，第编号 k 的区间的权值是不算进去的，
只能算后两个区间 k + 1 和 k + 2 区间的权值之和（但是你损耗了 3 个区间，而不是两个）。
只选择单个区间的时候也是一样，单个区间的权值算作 0。
#include <iostream>
#include <cstring>
using namespace std;const int inf = 99999999;
const int sleep = 1;
const int active = 0;long long DP[2][2][3900];
int utilities[3900];
int periods;
int can_be_used;void dp_solve(){for( int period = 2; period <= periods; ++period ){for( int used = 0; used <= can_be_used; ++used ){DP[period % 2][active][used] = max( DP[( period - 1 ) % 2][sleep][used],DP[( period - 1 ) % 2][active][used] );if( used > 0 )DP[period % 2][sleep][used] = max( DP[( period - 1 ) % 2][sleep][used - 1] + utilities[period],DP[( period - 1 ) % 2][active][used - 1] );elseDP[period % 2][sleep][used] = -inf;}}
}int main(){while( cin >> periods >> can_be_used ){for( int period = 1; period <= periods; ++period )cin >> utilities[period];for( int used = 0; used <= can_be_used; ++used ){DP[1][sleep][used] = -inf;DP[1][active][used] = -inf;}DP[1][active][0] = 0;DP[1][sleep][1] = 0;dp_solve();int ans1 = max( DP[periods % 2][sleep][can_be_used],DP[periods % 2][active][can_be_used] );for( int used = 0; used <= can_be_used; ++used ){DP[1][sleep][used] = -inf;DP[1][active][used] = -inf;}DP[1][sleep][1] = 0;dp_solve();int ans2 = max( DP[periods % 2][sleep][can_be_used] + utilities[1],DP[periods % 2][active][can_be_used] );int ans = max( ans1, ans2 );cout << ans << endl;}return 0;}
这篇关于POJ 2228 Naptime 环状DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
