P1880-[NOI1995]石子合并

蔚落 2023-06-01 08:51 60阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 typedef long long ll;
     4 using namespace std;
     5 inline ll read()
     6 {
     7     ll ans = 0;
     8     char ch = getchar(), last = ' ';
     9     while(!isdigit(ch)) last = ch, ch = getchar();
    10     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    11     if(last == '-') ans = -ans;
    12     return ans;
    13 }
    14 inline void write(ll x)
    15 {
    16     if(x < 0) x = -x, putchar('-');
    17     if(x >= 10) write(x / 10);
    18     putchar(x % 10 + '0');
    19 }
    20 int N;
    21 int a[309];
    22 int dp[309][309];
    23 int dp2[309][309];
    24 int pre[309];
    25 
    26 int main()
    27 {
    28     N = read();
    29     _for(i,0,N)
    30         a[i] = a[i+N] = read();
    31     
    32     memset(dp,0,sizeof(dp));
    33     _for(i,0,2*N-1)
    34         dp[i][i+1] = a[i]+a[i+1];
    35         
    36     memset(dp2,0,sizeof(dp2));
    37     _for(i,0,2*N-1)
    38         dp2[i][i+1] = a[i]+a[i+1];
    39     
    40     pre[0] = a[0];
    41     _for(i,1,2*N)
    42         pre[i] = pre[i-1]+a[i];
    43 
    44     for(int d = 3;d < N+1;d ++)
    45     {
    46         for(int i = 0;i < 2*N-d+1;i ++)
    47         {
    48             int j = i+d-1;
    49             dp2[i][j] = 0x3f3f3f3f;
    50             for(int k = i;k < j;k ++)
    51             {
    52                 dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]+pre[j]-pre[i]+a[i]);
    53                 dp2[i][j] = min(dp2[i][j],dp2[i][k]+dp2[k+1][j]+pre[j]-pre[i]+a[i]);
    54             }
    55         }
    56     }
    57     
    58     int rnt = 0;
    59     _for(i,0,N)
    60         rnt = max(rnt,dp[i][i+N-1]);
    61         
    62     int rnt2 = 0x3f3f3f3f;
    63     _for(i,0,N)
    64         rnt2 = min(rnt2,dp2[i][i+N-1]);
    65     write(rnt2);printf("\n");
    66     write(rnt);
    67     return 0;
    68 }

转载于:https://www.cnblogs.com/Asurudo/p/11330797.html