转自; 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;
}
|