轉(zhuǎn)自; http://blog.csdn.net/masterluo
記憶化DP。對(duì)于要取得最優(yōu)值，假設(shè)應(yīng)該釋放的排列為Q1, Q2, ……, Qn，我們?cè)诘谝淮畏指詈螅?-P分解成二個(gè)子問(wèn)題，1-（Q1-1）與（Q1+1）-P，這樣就把問(wèn)題分劃為更小的問(wèn)題，再遞歸進(jìn)行求解，然而在遞歸的過(guò)程中，許多問(wèn)題被重復(fù)計(jì)算，我們可以把己經(jīng)計(jì)算出來(lái)的區(qū)間最小值記錄下來(lái)，以后每次進(jìn)行分割時(shí)，如果某個(gè)段己經(jīng)求得最值就直接返回，否則進(jìn)行遞歸查找。
#include <stdio.h>
#include <map>
using namespace std;
const int maxn=110;
int p,q;
int id[maxn];
map<pair<int,int>,int>mp;
int solve(int l,int r)
{
pair<int,int>pr(l,r);
if(mp.find(pr)!=mp.end())
{
return mp[pr];
}
int ans=-1;
for(int i=0;i<q;i++)
{
if(id[i]>=l && id[i]<=r)
{
int tmp=r-l+solve(l,id[i]-1)+solve(id[i]+1,r);
if(ans==-1 || tmp<ans)
ans=tmp;
}
}
if(ans==-1) ans=0;
mp[pr]=ans;
return ans;
}
int main()
{
freopen("in","r",stdin);
freopen("myout","w",stdout);
int t;
scanf("%d",&t);
for(int i=1;i<=t;i++)
{
mp.clear();
scanf("%d%d",&p,&q);
for(int j=0;j<q;j++)
scanf("%d",&id[j]);
printf("Case #%d: %d\n",i,solve(1,p));
}
return 0;
}
|