題意：給你一些海龜，他們都有各自的重量和載重能力，要求把海龜堆成一落，要求每個(gè)海龜在稱(chēng)重的范圍之內(nèi)。
解法：感覺(jué)有點(diǎn)像背包問(wèn)題。用a[i][j]表示從前i個(gè)海龜中選擇j個(gè)的最小重量和，轉(zhuǎn)移方程為：a[i][j] = min(a[i-1][j],a[i-1][j-1]+t[i].st)(i>=j)，因?yàn)槊總€(gè)海龜不能超過(guò)其最大載重能力，所以第二個(gè)轉(zhuǎn)移方程的條件是a[i-1][j-1]<=t[i].st即前面i-1個(gè)海龜中選擇j-1個(gè)海龜?shù)淖钚≈亓坎荒艹^(guò)當(dāng)前海龜?shù)妮d重值。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define N 6000
#define INF 1 << 29
#define MIN(a, b) (a < b ? a : b)
struct turtle
{
int wt, st;
}t[N];
int a[N][N];
int cmp(turtle a, turtle b)
{
return a.st < b.st;
}
int main()
{
int n = 1, ans = 1;
while(~scanf("%d %d", &t[n].wt, &t[n].st))
{
t[n].st -= t[n].wt;
n++;
}
n--;
for(int i = 0; i <= n; i++)
for(int j = 0; j <= n; j++)
a[i][j] = INF;
for(int i = 0; i <= n; i++)
a[i][0] = 0;
std::sort(t + 1, t + n + 1, cmp);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
a[i][j] = a[i - 1][j];
if(a[i - 1][j - 1] <= t[i].st)
a[i][j] = MIN(a[i][j], a[i - 1][j - 1] + t[i].wt);
}
}
for(int i = n; i; i--)
if(a[n][i] < INF)
{
ans = i;
break;
}
printf("%d\n", ans);
return 0;
}