[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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology