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

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

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int inf=99999999;
const int maxn=550;

int dp[maxn][maxn],n,m;

void initial()
{
    memset(dp,0,sizeof(dp));
}

void input()
{
    scanf("%d %d",&n,&m);
}

void solve(int co)
{
    for(int k=2; k<=n; k++)
        for(int i=1,j=i+k-1; j<=n; j++,i++)
        {
            int ans=inf,tmp;
            for(int t=i; t<=j; t++)
            {
                tmp=(m+t)*k;
                if(t!=i) tmp+=dp[i][t-1];
                if(t!=j) tmp+=dp[t+1][j];
                ans=min(ans,tmp);
            }
            dp[i][j]=ans;
        }
    printf("Case %d: %d\n",co,dp[1][n]);
}

int main()
{
    int T;
    scanf("%d",&T);
    for(int co=1; co<=T; co++)
    {
        initial();
        input();
        solve(co);
    }
    return 0;
}

Uva 10688 The Poor Giant (区间DP)

原文：http://blog.csdn.net/u012596172/article/details/41119801