Akhmad228's blog

By Akhmad228, history, 7 years ago, In English

I have interesting problem from WCIP3G. I thought that is DP.

And in my DP I have 2 states.

dp[i][j] = answer for subsequence from i to j.

Transitions obviously will be dp[i + 1][j] and dp[i][j - 1].

But how it can be written?

Tags dp
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

#define rg register #define MAXN 110 int n; int dp[MAXN]; int sum[MAXN]; int main(){ ms(sum); read(n); for( rg int i = 1 ; i <= n ; i++ ){ read(dp[i]); sum[i] = sum[i-1] + dp[i]; } for( rg int i = n-1 ; i >= 1 ; i-- ) for( rg int j = i+1 ; j <= n ; j++ ){ rg int dp1 = sum[j] - sum[i-1] - dp[j]; rg int dp2 = sum[j] - sum[i-1] - dp[j-1]; dp[j] = max( dp1 , dp2 ); } printf("%d\n",dp[n] ); return 0; }
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks, but can you explain it?

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I used a algorithm called Sliding Array,which means"滚动数组" in Chinese. Besides this,my dp state is the same as yours. dp[i][j]=max(a[i]+sum[i+1][j]-dp[i+1][j], a[j]+sum[i][j-1]-dp[i][j-1]);

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can you tell what do sliding array in detail?

        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          "Sliding array" Means use a 1D array to store a 2D dp values

          You can just implementate my code,and you will know how it works!