大家一起来讨论
对动态规划还是迷迷糊糊，套用01的模版却不知道变通，希望可以抛砖引玉，可以吸引更多的人来讨论。
vec[i] 表示第i个歌的音高。
num[i][j] 表示 在第i首歌j调是否可以。
num[i][j] 与 num[i - 1][j - vec[i]] , num[i-1][j + vec[i]]有关。
#include <iostream>
#include <vector>
using namespace std;
int n,beL,maxL;
int num[60][1010];
vector<int> vec(60);
void dp(){
for(int i = 1; i <= n; i++){
for(int j = 0; j <= maxL; j++){
if(j - vec[i] >= 0){
if(num[i - 1][j - vec[i]]) {
num[i][j] = true;
}
}
if(j + vec[i] <= maxL){
if(num[i - 1][j + vec[i]]) {
num[i][j] = true;
}
}
}
}
for(int i = maxL; i >= 0; i--){
if(num[n][i]){
cout<<i<<endl;
return;
}
}
cout<< -1<<endl;
}
int main(){
cin>>n>>beL>>maxL;
for(int i = 1; i <= n; i++){
cin>>vec[i];
}
num[0][beL] = true;
dp();
return 0;
} 
查看17道真题和解析
