Educational Codeforces Round 83 E- Array Shrinking

人と違う解法(?)だったのでメモ書き

リンク

codeforces.com

問題概要

長さNの数列が与えられ、次の操作を何回でも行うことができる。

• 隣接する値が同じ項を選んで、取り除く。そしてそこに元の値+1の要素を挿入する

この時達成可能な数列の長さの最小値を求めよ

考察

なんか適当に貪欲をしたらダメだね→stackを持って、左から要素見て消せるなら消すだと[2,1,1,2,3,4,5]みたいなので反例となる。右から見ても同様の反例が存在。

ここで人々は区間DPを思いつくらしいです。

これが類題？　AOJ-ICPCのだるま落とし

https://onlinejudge.u-aizu.ac.jp/problems/1611

僕は区間を全て見て貪欲がダメなら、区間を全て試した時の貪欲はどうだろう？って考えに至りました。上の例だと[2,1,1][2,3,4,5]と見ると最善では無いが、[2][1,1,2,3,4,5]と見ると最善です。

dp[i][j]:区間(i,j]の区間の最小値として、全ての区間について求めた後はワーシャルフロイドの要領でdp[0][n]の最小値が求まります。

これで全体で求まります。

これは多分この問題に関しては正当性が示されているのですが、だるま落としに関してはこの解法が使えない気がしています。

後かいとさんの解をまだ僕は理解してないのでソースコードだけ勝手に紹介させて貰います。

Submission #72842498 - Codeforces

追記:解もあるらしい？？？まだ理解してない

Educational Round 83 problem E (Array Shrinking): O(n log n) solution - Codeforces

実装

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
typedef long long int ll;

int dp[550][550];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	vector<int> a(n);
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			if(i>=j){
				dp[i][j]=1e5;
			}else{
				dp[i][j]=j-i;
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=i+1;j<=n;j++){
			stack<int> st;
			for(int k=i;k<j;k++){
				int p=a[k];
				while(1){
					if(st.size()&&st.top()==p){
						st.pop();
						p++;
					}else{
						st.push(p);
						break;
					}
				}
			}
			dp[i][j]=st.size();
		}
	}
	for(int k=0;k<=n;k++){
		for(int i=0;i<=n;i++){
			for(int j=0;j<=n;j++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}
	cout << dp[0][n] << endl; 
}