Блог пользователя Akhmad228

Interesting problem
Автор Akhmad228, история, 7 лет назад, По-английски

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?

Теги dp
  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится 

#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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks, but can you explain it?

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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]);

      → Ответить