TIP

看问题角度的不同,对于一个问题的看法和解决步骤就不一样,虽然也许最后可以获得正确的答案,但是相比较而言要曲折很多。

今天做了一道题,题意大概是这样的,一个演奏家要演奏一首歌,这首歌开始的时候有一个初始音量,还有一个最大音量,在演奏过程中不允许音量小于0或者是大于最大音量。演奏家要表演这首歌很多次,每次s他可以选择是调低音量还是调高音量,但是这个改变的音量每次是不一样的,但是固定的。问演奏家最后一次演奏的最大音量是多少?如果在演奏过程中如何都不能保证音量在正常范围内,就输出-1。

这道题,开始我总是关注如何取得最大的音量,本身也是没有错的,但是对于这道题来说,想的就有点不对了。我想着,每次选择不是提高就是降低,这就有两种可能,依次往下推,就是一个二叉树,最后只需要遍历最底层的叶子节点,找到一个最大值,就可解决这个问题了。但是这样做的结果是,几乎都超时了。所以这个方法是不可行的,因为每次我都要保存任何计算的结果,太占用空间的时间了。

而另一个关注的角度,是关注与能不能到达这个音量,如果能是一种情况,如果不能又是一种情况,这个将会给解题带来很大方便,因为只需要关注,到演奏第i首歌的时候,能不能演奏这个音量,而不管这个是怎么来的。

#include<iostream>
#include<algorithm>
using namespace std;
int f[55][1005];
int main()
{
    int n,beginLevel,maxLevel;
   // freopen("in.txt","r",stdin);
    cin >> n >> beginLevel >>  maxLevel;
    for(int i=0;i<=n;i++){
        fill(f[i],f[i]+maxLevel,0);
    }
    f[0][beginLevel]=1;
    int m;
    for(int i=1;i<=n;i++){
        cin >> m;
        for(int j=maxLevel;j>=0;j--){
            if(j-m>=0){
                f[i][j] = f[i][j]||f[i-1][j-m];
            }
            if(j+m<=maxLevel){
                f[i][j] = f[i][j]||f[i-1][j+m];
            }
        }
    }
    int t=1;
    for(int i=maxLevel;i>=0;i--){
        if(f[n][i]==1){
            cout << i ;
            t=0;
            break;
        }
    }
    if(t){
        cout << "-1";
    }
  //  fclose(stdin);
    return 0;
}