[C++]白準1495番ギタリスト

質問する

Day Of MorningのギタリストKangtoが、間もなく来る公演のためにN曲を演奏している.これまでとは違った演出を披露するために、この公演は毎回、曲を開く前に音量を変えて演奏します.
まず、公演が始まる前に、各曲が始まる前に変更できる音量をリストします.このリストをVと呼ぶと、V[i]はi曲を演奏する前に変更できる音量を意味する.音量はリストの違いでしか変更できません.つまり、現在の音量がPであれば、現在のi曲を演奏する前に、i番曲はP+V[i]またはP-V[i]で演奏すべきである.ただし、ボリュームを0より小さい値またはMより大きい値に変更することはできません.
曲の数がN、開始音量S、Mの場合は、最後の曲を演奏できる音量のうち最も値を求めるプログラムを作成してください.すべての曲はリストの順番で演奏しなければならない.

入力

1行目はN S M(1≦N≦100,1≦M≦1000,0≦S≦M)第2行は、各曲の開始前に与えることができる音量差を与える.この値は1以上、またはM未満です.

しゅつりょく

1行目の最後の曲の音量で、最値を出力します.最後の曲を演奏できない場合(真ん中で音量を調節できない場合)、-1を出力します.

に答える

dp[i][j]i曲目まで演奏する場合、音量がjであれば1を保存し、そうでなければ0を保存する.音量は0からMにしか調整できないため、i+1曲を演奏する場合、j+arr[i]とj-arr[i]が0からMの間に存在する場合、dp[i+1]j+arr[i]とdp[i+1]j-arr[i]は1となる.
最終的に、dp[n][i]の値は1であり、iが最大のときのi値は最後の曲の音量の中で最も値である.

#include <iostream>
#include <vector>
#include <cstring>
#include <fstream>
#include <algorithm>
#include <cmath>
#define endl '\n'

using namespace std;

int n,s,m;
int dp[101][1001] = {0};
int arr[100];

int solve(){
  dp[0][s] = 1;

  for (int i=0; i<n; i++){
    for (int j=0; j<=1000; j++)
      if (dp[i][j]){
        if (j+arr[i] <= m) dp[i+1][j+arr[i]] = 1;
        if (j-arr[i] >= 0) dp[i+1][j-arr[i]] = 1;
      }
  }

  for (int i=1000; i>=0; i--)
    if (dp[n][i]){
      return i;
      break;
    }

  return -1;
}

int main(){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  // ifstream cin;
  // cin.open("input.txt");

  cin >> n >> s >> m;

  for (int i=0; i<n; i++){
    cin >> arr[i];
  }

  cout << solve();
}