[TIOJ]1997. 數列切割

題目連結：http://tioj.ck.tp.edu.tw/problems/1997

可以紀錄dp[n][k]代表前n個切了k刀，轉移式 dp[i][j] = max(dp[i-1][j],dp[i-1][j-1])+t*a[i]，當j是奇數t = -1，反之t = 1。

#include <iostream>
#define lld long long
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
using namespace std;
typedef pair<int,int> Pair;
lld dp[1000006][7];
int fa[1000006][7];
int main(){jizz
    int n,k;cin >> n >> k;k--;
    for(int i = 1 ; i <= n ; i++){
        int a,t;cin >> a;
        dp[i][0] = dp[i-1][0]+a;
        for(int j = 1 ; j <= k && j < i ; j++){
            t = (j&1 ? -1 : 1);
            if(j == i-1){
                fa[i][j] = i;
                dp[i][j] = dp[i-1][j-1]+t*a;
            }
            else if(dp[i-1][j]+t*a >= dp[i-1][j-1]+t*a){
                fa[i][j] = fa[i-1][j];
                dp[i][j] = dp[i-1][j]+t*a;
            }else{
                fa[i][j] = i;
                dp[i][j] = dp[i-1][j-1]+t*a;
            }
        }
    }
    while(k != 0){
        cout << fa[n][k]-1 << '\n';
        n = fa[n][k]-1;k--;
    }
    return 0;
}