JZOI-2885 切割钢条

题目描述

有一根长度为n米的钢条，要切割为若干小段，不同米数的小段价格也都不一样，现给出长为i米(1<=i<=n)小段的钢条价格ai,求将n米的钢条切割成整米数小段后所能卖到的最大价格。

输入

第1行，一个整数n（1<=n<=1000)。

第2行，n个空格隔开的整数ai(0<=ai<=1000)。

输出

一个整数，表示最大价格。

样例

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define ull unsigned long long
#define inf INT_MAX
#define uinf INT_MIN
#include 
using namespace std;
void p(register int a){
    if(a==1) putchar('\n');
    if(a==2) putchar(' ');
}
void write(register int x){
    if(x>=10) write(x/10);
    putchar(x%10+'0');
}           //快输
void read(register int &s){
    s=0;
    register bool flag=false;
    register char ch=getchar();
    while(!isdigit(ch)){
    if(ch=='-') flag=true;
    ch=getchar();
    }
    while(isdigit(ch)){
    s=s*10+ch-'0';
    ch=getchar();
    }
    if(flag) s*=-1;
}      //快读
int dp[1086];
int a[1086], n;
int main() //从main阅读程序是一个好习惯
{
    read(n);
    for(int i=1;i<=n;i++)
        read(a[i]);        //用快读输入切断钢条的费用
    dp[1]=a[1];        //第一位的钢条最小费用即为直接切一个单位长度
    for(int i=2;i<=n;i++)
    {
        int mini=uinf;        //认为这一位初始最小值为INT_MIN（-2147483648）
        for(int j=1;j<=min(i, n)/*避免负数组的出现*/;j++){
            mini=max(a[j]+dp[i-j], mini);        //状态转移方程 dp[i]=min(dp[i-1]+a[1], dp[i-2]+a[2], ...)
        }
        dp[i]=mini;//更新这一位的最小值
    }
    cout<