2012-11-18 18:06:31Morris
[UVA][烏龜塔] 10154 - Weights and Measures
這題是很著名的烏龜塔，做法是 dp，要對力量做升排序。
網路上好像有人提供力量減去自身重量的升排序，不過在下面兩隻烏龜的情形會有錯誤。
9 10
1 6
#include <stdio.h>
#include <algorithm>
using namespace std;
struct turtle {
int w, s;
};
bool cmp(turtle a, turtle b) {
return a.s < b.s;
}
int main() {
turtle A[5700];
int n = 0, i, j;
while(scanf("%d %d", &A[n].w, &A[n].s) == 2)
n++;
sort(A, A+n, cmp);
int dp[5700];
for(i = 0; i <= n; i++)
dp[i] = 0xfffffff;
dp[0] = 0;
for(i = 0; i < n; i++) {
for(j = n; j >= 1; j--) {
if(dp[j-1]+A[i].w <= A[i].s) {
dp[j] = min(dp[j], dp[j-1]+A[i].w);
}
}
}
for(i = n; i >= 0; i--) {
if(dp[i] != 0xfffffff)
break;
}
printf("%d\n", i);
return 0;
}
網路上好像有人提供力量減去自身重量的升排序，不過在下面兩隻烏龜的情形會有錯誤。
9 10
1 6
#include <stdio.h>
#include <algorithm>
using namespace std;
struct turtle {
int w, s;
};
bool cmp(turtle a, turtle b) {
return a.s < b.s;
}
int main() {
turtle A[5700];
int n = 0, i, j;
while(scanf("%d %d", &A[n].w, &A[n].s) == 2)
n++;
sort(A, A+n, cmp);
int dp[5700];
for(i = 0; i <= n; i++)
dp[i] = 0xfffffff;
dp[0] = 0;
for(i = 0; i < n; i++) {
for(j = n; j >= 1; j--) {
if(dp[j-1]+A[i].w <= A[i].s) {
dp[j] = min(dp[j], dp[j-1]+A[i].w);
}
}
}
for(i = n; i >= 0; i--) {
if(dp[i] != 0xfffffff)
break;
}
printf("%d\n", i);
return 0;
}