?

UVA_10154

?

? ? 首先，我們不妨證明一下這個(gè)命題，如果一個(gè)力量小的烏龜可以馱著一個(gè)力量大的烏龜，那么這個(gè)力量大的烏龜也必然可以馱起這個(gè)力量小的烏龜，而且還能夠使兩個(gè)烏龜上方增加承重能力。

?

? ? 我們不妨設(shè)力量小的烏龜?shù)闹亓亢土α糠謩e為w1、s1，而力量大的烏龜為w2、s2，由于烏龜1可以馱起烏龜2，那么有s1>=w1+w2，如果我們假設(shè)烏龜2馱不起烏龜1，那么就應(yīng)該有s2<w1+w2，然而我們知道烏龜2的力量更大，所以應(yīng)該有s2>s1>=w1+w2，這樣就產(chǎn)生矛盾了，原命題得證。

?

? ? 接著，如果烏龜1在烏龜2的下面，兩龜上方的承重能力至多為s1-(w1+w2)。然而如果換成烏龜2在烏龜1的下面的話，對(duì)于烏龜1來(lái)講是無(wú)所謂的，因?yàn)橹榜W得動(dòng)，現(xiàn)在少了烏龜2肯定也馱得動(dòng)，因此僅從烏龜1的承重限制來(lái)講，兩龜上方的承重能力增加了。當(dāng)然僅憑烏龜1的承重限制的角度來(lái)看是不全面的，我們還要考慮烏龜2，對(duì)于烏龜2來(lái)講，兩龜承重能力是s2-(w1+w2)，而前面也說(shuō)到了，烏龜1在下的時(shí)候承重能力至多為s1-(w1+w2)，而s2-(w1+w2)>s1-(w1+w2)，因此從烏龜2的角度來(lái)講，盡管上面多了個(gè)烏龜1，但就烏龜1和烏龜2作為整體而言，他們上方的承重能力也一定增加了。因此，無(wú)論兩龜整體的承重能力取決于哪只龜，調(diào)換之后最終的整體承重能力一定增加了。

?

? ? 于是這樣我們就可以先把烏龜按力量排序了，剩下的問(wèn)題就是怎么求這個(gè)最長(zhǎng)非降子序列了。

?

? ? 我們用max記錄最多能累的烏龜?shù)膫€(gè)數(shù)，顯然一開(kāi)始max應(yīng)該是0，再設(shè)f[j]表示烏龜一共累j個(gè)的時(shí)候的最輕的重量，那么顯然一開(kāi)始f[0]應(yīng)該為0，而其余的都應(yīng)為INF。

?

? ? 這樣對(duì)于當(dāng)前的烏龜i，如果f[j]+w[i]<s[i]且f[j]+w[i]<f[j+1]，那么我們就可以更新f[j+1]了，同時(shí)如果j+1比max要大的話，我們也需要同時(shí)更新max了。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXD 5700
#define INF 1000000000
int N, f[MAXD], w[MAXD], s[MAXD], r[MAXD];
int cmp(const void *_p, const void *_q)
{
int *p = (int *)_p;
int *q = (int *)_q;
return s[*p] - s[*q];
}
void init()
{
N = 0;
while(scanf("%d%d", &w[N], &s[N]) == 2)
{
if(s[N] >= w[N])
N ++;
}
}
void solve()
{
int i, j, max;
for(i = 0; i < N; i ++)
r[i] = i;
qsort(r, N, sizeof(r[0]), cmp);
for(i = 1; i <= N; i ++)
f[i] = INF;
f[0] = 0;
max = 0;
for(i = 0; i < N; i ++)
for(j = max; j >= 0; j --)
{
if(f[j] + w[r[i]] <= s[r[i]] && f[j] + w[r[i]] < f[j + 1])
{
f[j + 1] = f[j] + w[r[i]];
if(j + 1 > max)
max = j + 1;
}
}
printf("%d\n", max);
}
int main()
{
init();
solve();
return 0;
}

總結(jié)

以上是生活随笔為你收集整理的UVA 10154 Weights and Measures的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。