题目中没有给出重量和力量的范围，这似乎实在提醒我们：状态只和乌龟的个数有关！
a[i]为n个乌龟的重量，b[i]为n个乌龟的力量，定义d[i,j]表示从前i个乌龟中挑选出j个乌龟，j个乌龟的最小重量和为d[i,j]，这样就有如下状态转移方程：d[i,j]=min{d[i-1,j],d[i-1,j-1]+a[i]}(i>=j时状态有效，其中第二个转移方式的条件为d[i-1,j-1]<=b[i]-a[i])。
现在又有一个问题，题目中给出的序列是散乱的，无法保证最优子结构，所以要按照b[i]-a[i]递增的顺序排序。至于为什么要这么排序，我的认为是：只有这样才能使递推进行下去，试想如果不是这样，如何递推呢？
以下是我的代码：
#include<stdio.h>
#define maxn 5610
#define INF 10000000
#define min(a,b) (a<b?a:b)
long n=0,ans=0,a[maxn],b[maxn],d[maxn][maxn];
void Qsort(long begin,long end)
{
long i=begin,j=end,mid=b[(begin+end)/2],t;
do{
while(b[i]<mid) i++;
while(b[j]>mid) j--;
if(i<=j)
{
t=a[i];a[i]=a[j];a[j]=t;
t=b[i];b[i]=b[j];b[j]=t;
i++;j--;
}
}while(i<=j);
if(begin<j) Qsort(begin,j);
if(i<end) Qsort(i,end);
}
int main()
{
while(scanf("%ld%ld",&a[n+1],&b[n+1])==2)
{
n++;b[n]-=a[n];
}
// Read In
Qsort(1,n);
// Sort
for(long i=0;i<=n;i++)
for(long j=0;j<=n;j++)
d[i][j]=INF;
for(long i=0;i<=n;i++)
d[i][0]=0;
// Init
for(long i=1;i<=n;i++)
for(long j=1;j<=i;j++)
{
d[i][j]=min(d[i][j],d[i-1][j]);
if(d[i-1][j-1]<=b[i])
d[i][j]=min(d[i][j],d[i-1][j-1]+a[i]);
}
// DP
for(long i=n;i>=1;i--)
if(d[n][i]<INF)
{
ans=i;
break;
}
printf("%ld\n",ans);
return 0;
}
posted on 2010-02-22 16:26
lee1r 阅读(1797)
评论(13) 编辑 收藏 引用 所属分类:
题目分类：动态规划