AOJ 2430: Longest Increasing Sequence

解法

dp[index][分割する個数] := min{右端に来る数}
とするとO(N^3)でDPできるが、これでは間に合わないので、工夫して
dp[index][右端に来る数] := max{分割する個数}
として、j < k ⇒ dp[i][j] < dp[i][k] となるようなデータだけ持つようにすると、O(N^2logN)でDPできる。

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define N 4010
typedef long long ll;
typedef pair<ll, int> P;
ll d[N];
P s[N];
map<ll, int> dp[N];

int main(){
	int n;
	cin>>n;
	for(int i = 0; i < n; i++) scanf("%ld", d+i);
	ll sum = 0;
	for(int i = 0; i < n; i++){
		sum += d[i];
		ll sum2 = 0, cnt = 0;
		for(int j = i; j > 0; j--){
			sum2 += d[j];
			s[j-1] = P(sum2, j-1);
		}
		sort(s, s+i);
		for(int j = 0; j < i; j++){
			ll p = s[j].second, v = s[j].first;
			auto it = dp[p].upper_bound(-v);
			if(it == dp[p].end()) continue;
			int c = it->second;
			if(c <= cnt) continue;
			if(!dp[i].empty()){
				auto ite = dp[i].begin();
				if(ite->first == -v) dp[i].erase(ite);
			}
			cnt = c;
			dp[i][-v] = c+1;
		}
		if(dp[i].empty() || sum<-dp[i].rbegin()->first) dp[i][-sum] = 1;
	}

	int pos = n-2;
	auto it = dp[n-1].begin();
	int m = it->second, t = m, v = it->first;
	vector<int> res;
	while(t-->1){
		for(bool f = true; f; pos--){
			for(auto x: dp[pos]){
				if(x.second!=t) continue;
				if(x.first<=v) break;
				res.push_back(pos+1);
				f = false;
				break;
			}
		}
	}
	reverse(res.begin(), res.end());
	printf("%d\n", m);
	for(auto x: res) printf("%d ", x);
	puts("");

	return 0;
}