随便's Blog

Description

一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。
音量用一个整数描述。输入文件中给定整数beginLevel，代表吉他刚开始的音量，以及整数maxLevel，代表吉他的最大音量。音量不能小于0也 不能大于maxLevel。输入文件中还给定了n个整数c1,c2,c3…..cn，表示在第i首歌开始之前吉他手想要改变的音量是多少。
吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。

动态规划 定义bool型 f【第i首歌】【音量】 如果当前可以达到就用它更新下一首歌的状态。

/**************************************************************
    Problem: 2748
    User: 1115825064
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1328 kb
****************************************************************/
 
#include<iostream>
#include<cstring>
#include<cstdio>
 
using namespace std;
 
int ma,n;
bool f[55][1010];
 
int main()
{
//  freopen("1.txt","r",stdin);
    int aa;
    scanf("%d%d%d",&n,&aa,&ma);
    f[0][aa]=1;
    for(int i=0;i<n;++i)
    {
        int c;
        scanf("%d",&c);
        for(int j=0;j<=ma;++j)
        { 
            if(f[i][j])
            {
                if(j+c<=ma) f[i+1][j+c]=1;
                if(j-c>=0) f[i+1][j-c]=1;
            }
        }
    }
    int a=-1;
    for(int j=0;j<=ma;++j)
    {
        if(f[n][j])
            a=j;
    }
    printf("%d",a);
    return 0;
         
}