你將要在元旦演奏一場吉他專場。但你不希望聲音平淡，所以你希望每個曲之間都有變化?，F在你已經確定了每個曲可以與上一個曲之間的音量的變化量，即每首曲開始，你可以對音量選擇增加或減少一個指定的變化值。當然音量不可能為負數，也不能太高，因此必需保證每首曲音量在0和maxLevel之間（包含）。你的任務是，根據已有的開始音量beginLevel 和每首曲之間的變化量，求出最后一首曲的最大可能音量。如果沒有方案，輸出 -1。［輸入文件：song.in］文件第一行有三個整數，n, beginLevel, maxLevel，分別表示曲目數，開始量，最大限制音量。下面有n-1行整數，第i行整數表示第i首曲與第i+1首曲之間的變化量。［輸入文件：song.in］文件只一行一個數，答案。[樣例：]4 5 105375 8 2015291010-1【數據范圍】1<=n<=100;1<= maxLevel <=10000<= beginLevel <= maxLevel
1 回答
ITMISS
TA貢獻1871條經驗 獲得超8個贊
#include <iostream>
using namespace std;
int n;
int begin_Level, max_Level;
int res, value[100];
// 深度優先搜尋
void dfs(int t, int k = 1)
{
if( t<0 || t>max_Level )
return;
if( k == n ){
if( t>res && t>=0 && t<=max_Level )
res = t;
return;
}
t -= value[k]; // try -
dfs(t, k+1);
t += value[k];
t += value[k]; // try +
dfs(t, k+1);
t -= value[k];
}
int main()
{
// 若有要求輸入輸出文件，自行解決
while( cin >> n >> begin_Level >> max_Level )
{
res = -1;
for(int i = 1; i < n; ++i)
cin >> value[i];
dfs(begin_Level);
cout << res << endl;
}
return 0;
}
- 1 回答
- 0 關注
- 648 瀏覽