轉自; http://blog.csdn.net/masterluo
記憶化DP。對于要取得最優值，假設應該釋放的排列為Q1, Q2, ……, Qn，我們在第一次分割后，1-P分解成二個子問題，1-（Q1-1）與（Q1+1）-P，這樣就把問題分劃為更小的問題，再遞歸進行求解，然而在遞歸的過程中，許多問題被重復計算，我們可以把己經計算出來的區間最小值記錄下來，以后每次進行分割時，如果某個段己經求得最值就直接返回，否則進行遞歸查找。
#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;
}
|