我很少寫(xiě)較長(zhǎng)的題解，但是對(duì)于這一題我覺(jué)得很有必要。
對(duì)于這道題，首先應(yīng)該想到貪心：每次取差值最小的一對(duì)。但是這樣的貪心策略很容易找到反例，而且N=5000的數(shù)據(jù)規(guī)模，十分有可能是O(n^2)的算法。
于是考慮動(dòng)態(tài)規(guī)劃。如果是DP，那么很容易想到如下的狀態(tài)定義：d[i][j]表示用前j個(gè)數(shù)組成i個(gè)(x,y,z)數(shù)對(duì)的最小消耗。
另外一個(gè)很容易注意到的地方就是：對(duì)于一個(gè)最優(yōu)決策中的任意一個(gè)數(shù)對(duì)(x,y,z)，其中x和y必在有序的a[i]中相鄰。關(guān)于這點(diǎn)用反證法不難證明，也很容易注意到。
對(duì)于(x,y,z)中的z應(yīng)該如何決策的問(wèn)題，之前一直令我迷惑，這一點(diǎn)應(yīng)該是題目最難解決的問(wèn)題。
考慮狀態(tài)d[i][j]:
對(duì)于x和y，有如下考慮：
對(duì)于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])；
于是有了總的狀態(tài)轉(zhuǎn)移方程：d[i][j]=min{d[i][j-1],d[i-1][j-2]+w(a[i],a[i-1])}；
這應(yīng)該不難理解，但是對(duì)于z的決策呢？
如果把a(bǔ)[i]按降序排列，那么z的影響就可以忽略了！這樣依然可以采用上面的方程。
考慮狀態(tài)d[i][j]：
如果j<3i，此時(shí)當(dāng)前策略是不可行的，d[i][j]=INF；
如果j>=3i，即j>=3(i-1)+3，j>3(i-1)+2，當(dāng)前狀態(tài)有效
轉(zhuǎn)移到d[i-1][j-2]時(shí)，至少剩余一個(gè)多余的a[k]
由于序列降序，a[k]可以和a[j]、a[j-1]配對(duì)
同時(shí)d[i-1][j-2]有效，可以繼續(xù)遞歸。
轉(zhuǎn)移到d[i][j-1]
若d[i][j-1]為無(wú)效狀態(tài)，d[i][j-1]==INF，必然不會(huì)比上面那種轉(zhuǎn)移方式優(yōu)；
若d[i][j-1]為有效狀態(tài)，可以繼續(xù)遞歸地進(jìn)行下去。
以下是我的代碼，采用的記憶化搜索：
#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)
評(píng)論(2) 編輯 收藏 引用 所屬分類(lèi):
題目分類(lèi)：動(dòng)態(tài)規(guī)劃