bzoj2748 haoi2012音量調節

​​http://www.elijahqi.win/archives/520​​​

題目描述

一個吉他手準備參加一場演出。他不喜歡在演出時始終使用同一個音量，是以他決定每一首歌之前他都需要改變一次音量。在演出開始之前，他已經做好一個清單，裡面寫着每首歌開始之前他想要改變的音量是多少。每一次改變音量，他可以選擇調高也可以調低。

音量用一個整數描述。輸入檔案中整數beginLevel，代表吉他剛開始的音量，整數maxLevel，代表吉他的最大音量。音量不能小于0也不能大于maxLevel。輸入中還給定了n個整數c1,c2,c3,…,cn，表示在第i首歌開始之前吉他手想要改變的音量是多少。

吉他手想以最大的音量演奏最後一首歌，你的任務是找到這個最大音量是多少。

輸入輸出格式

輸入格式：

第一行依次為三個整數n, beginLevel, maxLevel。

第二行依次為n個整數 c1,c2,c3,…,cn。

資料規模：

1<=n<=50, 1<=ci<=maxLevel, 1<=maxLevel<=1000, 0<=beginLevel<=maxLevel

輸出格式：

輸出演奏最後一首歌的最大音量。如果吉他手無法避免音量低于0或者高于maxLevel，輸出-1。

#include<cstdio>
int f[55][1100],a[55],n,begin,maxlevel; 
inline int read(){
    int x=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
int main(){
    freopen("1877.in","r",stdin);
    n=read();begin=read();maxlevel=read();
    for (int i=1;i<=n;++i) a[i]=read();f[0][begin]=1;
    for (int i=1;i<=n;++i)
        for (int j=0;j<=maxlevel;++j){
            int tmp1=j-a[i],tmp2=j+a[i];
            if (tmp1>=0&&f[i-1][tmp1]==1) f[i][j]=1;
            if (tmp2<=maxlevel&&f[i-1][tmp2]==1) f[i][j]=1;
        }
    for (int i=maxlevel;i>=0;--i) if (f[n][i]==1) {printf("%d",i);return 0;}
    printf("-1");
    return 0;
}