桐桐的爬山计划(nhoi2007tg1)

传统题

时间限制：1000ms

空间限制：128MiB

说明

桐桐一直有个梦想，他一直都很希望他能像“蜘蛛人”罗伯特一样。所以为了达成这个梦想，桐桐每天都辛勤的练习攀爬。练习的出发点与最终的点都是在地上面。给出一个数列，代表他每次移动的距离。这个移动可以向上，也可以是向下。但他是不可能到达地下面去的。而他做练习使用的建筑物总是比他到达过的最高的位置高2米。现在我们希望这个建筑物的高度越小越好。

如：

20 20 20 20

如果是 上，上，下，下 的话，这个建筑物就要42米高，如果是 上，下，上，下 就只要22米高。 当然有些数列是无解的。例如下面这个：

3 4 2 1 6 4 5

Input

第一行输入n(n<=100)，代表有n个爬行距离

第二行输入n个爬行距离(均为整数)，这些爬行距离的总和不超过10000

Output 如果有解，则输出最小的高度 否则输出"IMPOSSIBLE"

Sample Input

4

20 20 20 20

Sample Output

22

贴个错误代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,ml,a[1000005],dp[105][10005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],ml+=a[i];
    memset(dp,127,sizeof dp);
    dp[0][0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<=ml;j++)
            if(dp[i][j]!=2139062143){
                if(j-a[i+1]>=0) dp[i+1][j-a[i+1]]=min(dp[i+1][j-a[i+1]],max(dp[i][j],j-a[i+1]));
                if(j+a[i+1]<=ml) dp[i+1][j+a[i+1]]=min(dp[i+1][j+a[i+1]],max(dp[i][j],j+a[i+1]));
            }
    }
    if(dp[n][0]!=2139062143) cout<<dp[n][0]+2;
    else cout<<"IMPOSSIBLE";
    return 0;
}

rt求调

此帖代 @linruyi 发