C2-Zexal的钢管切割

题目描述

在钢管切割的背景下，已经知道长度为1−n">1?n的钢管的价值，给定长度为n">n的钢管在切割若干次（也可以不切割）所带来的最小价值是？

输入

多组数据输入

第一行一个整数n">n，为起始钢管长度（0<n≤1000">0<n≤1000）

第二行n">n个整数，分别为长度为i">i的钢管的价值ti">ti（0<ti≤106">0<ti≤10^6）

输出

对于每组数据，输出一行，为这根钢管所带来的最小价值T">T

输入样例

3
2 3 7

输出样例

 5

Hint

算法导论第三版15.1节

转移方程

dp[i] = min(dp[i-j] + dp[j], dp[i]);

代码

#include 
#include 
using namespace std;
long long n,dp[1003];
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&dp[i]);
        }
        for(int i = 1; i <= n; i++)
            for(int j = 1; j < i; j++)
                dp[i] = min(dp[i-j] + dp[j], dp[i]);
        printf("%d\n",dp[n]);
    }
    return 0;
}