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;
}