PKU 3016 K-Monotonic

単調増加列用と単調現象列用にすこしずらした配列を持ってあとは典型的なやつ。
あとはまとめて計算してオーダーを落とすタイプのDP。

#include<stdio.h>
#include<algorithm>
using namespace std;
int c[1500]; // use in increasion
int d[1500]; // use in decreasion
int C[1500];
int D[1500];
int dp[2][2][1500][12];
int ABS(int a){
	return max(a,-a);
}
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		for(int i=0;i<a;i++)scanf("%d",c+i);
		for(int i=0;i<a;i++){
			d[i]=c[i]-(a-1-i);
			c[i]=c[i]-i;
			C[i]=c[i];
			D[i]=d[i];
		}
		std::sort(C,C+a);
		std::sort(D,D+a);
		for(int i=0;i<=a;i++)
			for(int j=0;j<=b;j++)
				dp[0][0][i][j]=dp[0][1][i][j]=dp[1][0][i][j]=dp[1][1][i][j]=999999999;
		dp[0][0][0][0]=0;
		for(int i=0;i<a;i++){
			int t=i&1;
			for(int j=0;j<=a;j++)
				for(int k=0;k<=b;k++)
					dp[!t][0][j][k]=dp[!t][1][j][k]=999999999;
			for(int j=0;j<=b;j++){
				int v=999999999;
				for(int k=0;k<a;k++)v=min(v,min(dp[t][0][k][j],dp[t][1][k][j]));
				// new one
				if(j<b)
				for(int k=0;k<a;k++){
					dp[!t][0][k][j+1]=v+ABS(c[i]-C[k]);
					dp[!t][1][k][j+1]=v+ABS(d[i]-D[k]);
				}
				// old one
				if(i==0)continue;
				int now=999999999;
				for(int k=0;k<a;k++){
					now=min(now,dp[t][0][k][j]);
					dp[!t][0][k][j]=min(dp[!t][0][k][j],now+ABS(c[i]-C[k]));
				}
				now=999999999;
				for(int k=a-1;k>=0;k--){
					now=min(now,dp[t][1][k][j]);
					dp[!t][1][k][j]=min(dp[!t][1][k][j],now+ABS(d[i]-D[k]));
				}
			}
		}
		int ret=999999999;
		for(int i=0;i<a;i++){
			ret=min(ret,dp[a&1][0][i][b]);
			ret=min(ret,dp[a&1][1][i][b]);
		}
		printf("%d\n",ret);
	}
}