[USACO 09 MAR]Cleeaning Up題解を整理する(DP良い問題)

今日はfyオーディエンスから素晴らしいDP問題を聞きました.他の多くのDPと違って、簡単な移行方式とデータ構造の最適化によって、これらの問題は一つのデータ構造の暴力問題にもっと接近します.しかし、この問題の絶妙な点は、いかなるデータ構造を使用する必要はないということです.最適化の巧妙さは、データ構造の暴力的維持による複雑さの減少よりも、配列自体の性質に重点を置いています.
送信ゲート
一つの長さはnの数列で、それを任意の区間に分けて、価格と最小化します.ここで価格を定義すると、区間の数の平方を意味します.最小値を出力します.
簡単な分析を経て、状態移行方程式:dp[i]=min(dp[i],dp[j]+w[i]、[j]^2)、dp[i]は位置iの前の数を指す対価最小値を導出した.w[i][j]は区間[i,j]内の数字の種類数を意味します.そこで,複雑度O(n^2)のアルゴリズムを得て,50%ぐらいのデータを得ることができた.
暴力DPコードは以下の通りです.

#include 
using namespace std;
const int SIZE=40005;
const int INF=0x3f3f3f3f;

int n,m,cnt=0;
int a[SIZE],col[SIZE],dp[SIZE];

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	memset(dp,INF,sizeof(dp));
	memset(col,0,sizeof(col));
	dp[0]=0;
	
	for (int i=1;i<=n;i++){
		cnt=0;
		memset(col,0,sizeof(col));
		for (int j=i;j>=1;j--){
			if (!col[a[j]]){
				col[a[j]]=1;
				cnt++;
			}
			dp[i]=min(dp[i],dp[j-1]+cnt*cnt);
		}
	}
	
	printf("%d",dp[n]);
	
	return 0;
}

実測:洛谷で50点の好成績を得られます.
試験場ではいいはずですが、正解をもっと求めましょう.
実は正解からもう遠くないです.無数の部分を漕ぐことができますので、人はそれぞれの数を単独でグループと呼ぶことができます.価格と1^2*n=nを得ることができます.つまり、各グループの数に対して、答えはきっとnより小さいです.明らかに、一つの区間の数の種類がsqrt(n)を超えたら、価格はnを超えますが、上から答えはきっとn以下になります.だから、一つの区間の数の種類はsqrt(n)に相当します.そこで、配列pos[i]を一つ作って、i番目の以前の種類数がiの一番遠い位置を表します.そこで、新しいdp方程式を得ました.dp[i]=min(dp[i],dp[p[j]-1]+j*j)は、jを規定しています.
どのように素早くpos行列を更新するかについては、「四保一」技術、つまり4つの配列を使って互いに維持して目標配列を維持することができます.具体的には、pre[i]はi番目の数字が前回現れた位置を表し、next[i]はi番目の数字が次に現れた位置を表し、この2つの配列の間でi番目の数字は一回だけ現れます.つまり、区間(pre[i],next[i])内の数字a[i]は1回だけ現れます.last[i]は数字iの最後の出現位置を表し、下界を判断することができる.cnt[i]は現在のpos[i]の出現回数を表します.pre[i]jの場合、pos[j]は右に移動して、それが現れたことを保証します.nextは同じです.lastは境界を判断します.

#include 
using namespace std;
const int SIZE=40005;
const int INF=0x3f3f3f3f;

int n,m;
int a[SIZE],dp[SIZE],pre[SIZE],next[SIZE],last[SIZE],cnt[SIZE],pos[SIZE];

void clear()
{
	for (int i=1;i<=n;i++){
		pre[i]=last[a[i]];
		next[last[a[i]]]=i;
		last[a[i]]=i;
		next[i]=n+1;
	}
	
	for (int i=1;i<=sqrt(n);i++)
		pos[i]=1;
	
	memset(dp,INF,sizeof(dp));
	
	dp[0]=0;
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	
	clear();
	
	for (int i=1;i<=n;i++)
		for (int j=1;j<=(int)sqrt(n);j++){
			if (pre[i]j){
				while (next[pos[j]]