2502:VOCAL ANDROID
動的計画法で解いた。
dp[i]:=長さiのメロディの得点の最大値
#include<iostream> #include<algorithm> using namespace std; int main(void){ int n,m,s[400],l[400],p[400],w[400],dp[400]; cin >> n; for(int i=0;i<n;i++) cin >> s[i] >> l[i] >> p[i]; cin >> m; for(int i=0;i<m;i++)cin >> w[i]; fill(dp,dp+400,-1); dp[0]=0; for(int i=1;i<400;i++) for(int j=0;j<n;j++) for(int k=s[j];k<=l[j];k++) if(i-k>=0)dp[i]=max(dp[i],dp[i-k]+p[j]); for(int i=0;i<m;i++){ if(dp[w[i]]<0){ cout << -1 << endl; return 0; } } for(int i=0;i<m;i++) cout << dp[w[i]] << endl; return 0; }