結果

提出番号	979
提出者	ei1333
言語	C++
提出日時	2017-08-01 23:51:08
問題名	(25)Range of Influence
結果	TLE
点数	0%

---

テストケース

ソースコード

#include<bits/stdc++.h>

using namespace std;

const int INF = 1 << 30;

int N, A[3000], B[3000];
int dp[3000][3000];
int sum[3001];

int main()
{
  cin >> N;
  for(int i = 0; i < N; i++) cin >> A[i];
  for(int i = 0; i < N; i++) cin >> B[i];

  for(int i = 0; i < N; i++) sum[i + 1] += sum[i] + A[i];

  fill_n(*dp, 3000 * 3000, INF);
  for(int i = 0; i < N; i++) dp[i][i] = B[i];

  for(int i = 2; i <= N; i++) {
    for(int j = 0; j <= N - i; j++) {
      int k = j + i - 1; // [j, k]

      for(int l = j; l <= k; l++) {
        int L1 = j, R1 = l - 1, L2 = l + 1, R2 = k;

        int sum1 = sum[R1 + 1] - sum[L1];
        int sum2 = sum[R2 + 1] - sum[L2];

        if(sum1 >= sum2) dp[j][k] = min(dp[j][k], dp[L1][R1] + B[l]);
        else dp[j][k] = min(dp[j][k], dp[L2][R2] + B[l]);
      }
    }
  }

  cout << dp[0][N - 1] << endl;
}