[TIOJ] 1997. 數列切割

題目連結:http://tioj.infor.org/problems/1997

---

校內複賽的時候只喇到$k \leq 3$的測資，不過感覺這題是DP，只是賽中一直想不太出來，後來被雷了才知道這題的做法...
狀態設成$dp[i][j]$代表用前$i$個湊出$j$組的最大值可能為多少，而很明顯知道若是現在再加一個數，可以選擇的就是變成$dp[i+1][j+1]$或$dp[i+1][j]$，所以就照著這DP下去就好了，然後記得判一下奇偶之類的。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef pair<int,int> PII;
#define FF first
#define SS second
const int N = 1000000 + 5;
const lld INF = 1LL<<40;

int arr[N];
lld dp[N][7];
PII ori[N][7];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, k; cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>arr[i];
	fill(dp[1], dp[n]+7, -INF);
	dp[1][1]=arr[1];
	for(int j=1;j<=k;j++){
		for(int i=j;i<n;i++){
			if(j&1){
				if(dp[i][j]+arr[i+1] > dp[i+1][j]){
					dp[i+1][j] = dp[i][j]+arr[i+1];
					ori[i+1][j] = {i, j};
				}
				if(i >= j and dp[i][j]-arr[i+1] > dp[i+1][j+1]){
					dp[i+1][j+1] = dp[i][j]-arr[i+1];
					ori[i+1][j+1] = {i, j};
				}
			}else{
				if(dp[i][j]-arr[i+1] > dp[i+1][j]){
					dp[i+1][j] = dp[i][j]-arr[i+1];
					ori[i+1][j] = {i, j};
				}
				if(i >= j and dp[i][j]+arr[i+1] > dp[i+1][j+1]){
					dp[i+1][j+1] = dp[i][j]+arr[i+1];
					ori[i+1][j+1] = {i, j};
				}
			}
		}
	}
	while(n!=0 and k!=0){
		int nn = ori[n][k].FF, kk = ori[n][k].SS;
		if(k!=kk and nn!=0) cout<<nn<<'\n';
		n=nn, k=kk;
	}
	return 0;
}