我很少寫較長的題解，但是對于這一題我覺得很有必要。
對于這道題，首先應該想到貪心：每次取差值最小的一對。但是這樣的貪心策略很容易找到反例，而且N=5000的數據規模，十分有可能是O(n^2)的算法。
于是考慮動態規劃。如果是DP，那么很容易想到如下的狀態定義：d[i][j]表示用前j個數組成i個(x,y,z)數對的最小消耗。
另外一個很容易注意到的地方就是：對于一個最優決策中的任意一個數對(x,y,z)，其中x和y必在有序的a[i]中相鄰。關于這點用反證法不難證明，也很容易注意到。
對于(x,y,z)中的z應該如何決策的問題，之前一直令我迷惑，這一點應該是題目最難解決的問題。
考慮狀態d[i][j]:
對于x和y，有如下考慮：
對于a[j]，如果不使用a[j]，那么d[i][j]=d[i][j-1]；
如果使用a[j]，那么就和a[j-1]一起使用，d[i][j]=d[i-1][j-2]+w(a[i],a[i-1])；
于是有了總的狀態轉移方程：d[i][j]=min{d[i][j-1],d[i-1][j-2]+w(a[i],a[i-1])}；
這應該不難理解，但是對于z的決策呢？
如果把a[i]按降序排列，那么z的影響就可以忽略了！這樣依然可以采用上面的方程。
考慮狀態d[i][j]：
如果j<3i，此時當前策略是不可行的，d[i][j]=INF；
如果j>=3i，即j>=3(i-1)+3，j>3(i-1)+2，當前狀態有效
轉移到d[i-1][j-2]時，至少剩余一個多余的a[k]
由于序列降序，a[k]可以和a[j]、a[j-1]配對
同時d[i-1][j-2]有效，可以繼續遞歸。
轉移到d[i][j-1]
若d[i][j-1]為無效狀態，d[i][j-1]==INF，必然不會比上面那種轉移方式優；
若d[i][j-1]為有效狀態，可以繼續遞歸地進行下去。
以下是我的代碼，采用的記憶化搜索：
#include<stdio.h>
#include<string.h>
const long maxn=5007,INF=100000007;
long k,n,r[maxn],d[1007][maxn],w[maxn];
long min(long a,long b)
{
return (a<b?a:b);
}
void swap(long &a,long &b)
{
long t=a;a=b;b=t;
}
long dp(long kk,long nn)
{
if(d[kk][nn]!=-1)
return d[kk][nn];
if(nn<3*kk)
d[kk][nn]=INF;
else if(kk==0)
d[kk][nn]=0;
else
{
d[kk][nn]=INF;
d[kk][nn]=min(dp(kk,nn-1),dp(kk-1,nn-2)+w[nn]);
}
return d[kk][nn];
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
long test;
scanf("%ld",&test);
while(test--)
{
scanf("%ld%ld",&k,&n);k+=8;
for(long i=1;i<=n;i++)
scanf("%ld",&r[i]);
// Input
for(long i=1,j=n;i<j;i++,j--)
swap(r[i],r[j]);
for(long i=2;i<=n;i++)
w[i]=(r[i]-r[i-1])*(r[i]-r[i-1]);
for(long i=0;i<=k;i++)
for(long j=0;j<=n;j++)
d[i][j]=-1;
// Init
// DP
printf("%ld\n",dp(k,n));
}
return 0;
}
posted on 2010-02-19 21:01
lee1r 閱讀(1424)
評論(2) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃