這個題個人認為是我目前所做的最難的區間dp了，以前把環變成鏈的方法在這個題上并不能使用，因為那樣可能存在重復計算
我第一遍想的時候就是直接把環變成鏈了，wa了5個點，然后仔細思考一下就發現了問題
比如這個樣例
5 4
1 2 4 1 1
這個樣例變成鏈以后就是這樣
1 2 4 1 1 1 2 4 1 1
在這個鏈上，很明顯，取[2,3]和[7,8]是最優方案，答案是8，但是很容易可以算出，這個樣例真正答案是7，2+4+1。
因此這個方法是不可行的，我在查閱了網上唯一的題解發現，這個問題可以灰常巧妙的用初始賦值來解決，我們可以進行兩遍遞推，第一遍認為第一個點不可以被加進答案，第二遍認為第二個點可以被加進答案
第一遍非常好理解，是基于不考慮時間成環的，第二個有點難想，假如第一個點能選，則說明至少在原序列終點及以前以前有個點是賣萌開始的起始點
那么我們處理的時候，會認為在原序列上，從真實的起始點一直到最后原序列終點被選了
比如這個樣例
5 3
5 1 1 1 3
1 0 0 1 1 0為未選擇，1為選擇
答案是8，第二遍遞推會認為1-1,4-5這兩個區間合起來是答案，就是這樣來保證正確性的。
#include<iostream> #include<cstdio> using namespace std; int n,m,dp[2][3610][2],qwq[7210],ans,t; inline void init() {for(int j=0;j<=m;j++)dp[0][j][0]=dp[0][j][1]=dp[1][j][0]=dp[1][j][1]=-1e9; } void dp1() {t=0;for(int i=2;i<=n;i++){t=1-t;for(int j=0;j<=m;j++){dp[t][j][0]=max(dp[1-t][j][0],dp[1-t][j][1]);if(j>0)dp[t][j][1]=max(dp[1-t][j-1][0],dp[1-t][j-1][1]+qwq[i]);}} } int main() {scanf("%d%d",&n,&m);if(m<=1)//特判一下，如果賣萌時間就給了1或0，答案一定為0 {printf("0");return 0;}for(int i=1;i<=n;i++)scanf("%d",&qwq[i]);init();//預處理，需要用滾動數組優化時間 dp[0][1][1]=dp[0][0][0]=0;//當沒有從最后一個位置開始的時候，第一個時段答案肯定為0 dp1();ans=max(dp[t][m][0],dp[t][m][1]);//在最后時段取與不取之間找個最大值 init();dp[0][1][0]=dp[0][1][1]=qwq[1];//當從最后一個時段開始的時候 dp1();//進行兩遍遞推 ans=max(ans,dp[t][m][1]);printf("%d",ans); }
?
)
