題目中沒有給出重量和力量的范圍，這似乎實在提醒我們：狀態只和烏龜的個數有關！
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 閱讀(1814)
評論(13) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃