[UVA][dp] 10688 - The Poor Giant
Problem A
The Poor Giant
Input: Standard Input
Output: Standard Output
Time Limit: 1 second
On a table, there are n apples, the i-th apple has the weight
k+i(1<=i<=n). Exactly one of the apples is sweet, lighter apples
are all bitter, while heavier apples are all sour.
The giant wants to know which one is sweet, the only thing he can do is
to eat apples. He hates bitter apples and sour apples, what should he
do?
For examples, n=4, k=0, the apples are of weight 1, 2, 3, 4.
The gaint can first eat apple #2.
if #2 is sweet, the answer is #2
if #2 is sour, the answer is #1
if #2 is bitter, the answer might be #3 or #4, then he eats #3, he'll know the answer regardless of the taste of #3
The poor gaint should be prepared to eat some bad apples in order to
know which one is sweet. Let's compute the total weight of apples he
must eat in all cases.
#1 is sweet: 2
#2 is sweet: 2
#3 is sweet: 2 + 3 = 5
#4 is sweet: 2 + 3 = 5
The total weights = 2 + 2 + 5 + 5 = 14.
This is not optimal. If he eats apple #1, then he eats total weight of
1, 3, 3, 3 when apple #1, #2, #3 and #4 are sweet respectively. This
yields a solution of 1+3+3+3=13, beating 14.
What is the minimal total weight of apples in all cases?
Input
The first line of input contains a single integer t(1<=t<=100), the number of test cases. The following t lines each contains a positive integer n and a non-negative integer k(1<=n+k<=500).
Output
For each test case, output the minimal total weight in all cases as shown in the sample output.
Sample Input | Sample Output |
5 2 0 3 0 4 0 5 0 10 20 |
Case 1: 2 Case 2: 6 Case 3: 13 Case 4: 22 Case 5: 605 |
Problem setter: Rujia Liu, Member of Elite Problemsetters' Panel
題目描述：//這題感覺就直接在描述算法本身盤面上有 n 顆蘋果，第 i 顆蘋果的成本是 k+i。這裡希望妳找到一顆甜的蘋果，
當吃掉第 i 顆蘋果時，倘若是酸的，則甜的會出現在 < i 的地方。
反之如果是苦的話，則甜的會出現在 > i 的地方。記住，搜索時吃掉會耗成本的。
給定 n, k 之後，只利用同一種策略，當甜的蘋果出現在任何位置，其所有位置成本總合最小。
題目解法：
可以把 k 當作 base 看待，那麼對於 dp[n][k] 可以決策第一步應該在哪裡？
則 dp[n][k] = min(n*(k+i) + dp[i-1][k] + dp[n-i][k+i]);
如果選擇第 i 顆蘋果做為第一步，那麼對於剩餘位置都會造成 k+i 的成本，因此消耗 n*(k+i)。
然後必須加上答案在左邊的情況，此時 base 不用動。但是在右邊時，base 變成 k+i。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int dp[505][505];
int dfs(int n, int k) {
int &v = dp[n][k];
if(v != -1) return v;
if(n <= 1) return 0;
int i, tmp;
v = 0xfffffff;
for(i = 1; i <= n; i++) {
tmp = n*(k+i) + dfs(i-1, k) + dfs(n-i, k+i);
v = min(v, tmp);
}
return v;
}
int main() {
memset(dp, -1, sizeof(dp));
int t, cases = 0, n, k;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &k);
printf("Case %d: %d\n", ++cases, dfs(n, k));
}
return 0;
}