NOI1995 石子合并

2018/09/01 23:39

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('\n')
using namespace std;
typedef long long ll;
const int M = 205;
int n,L,a[M],dp1[M][M],dp2[M][M],q[M],sum[M],minn = 1000000007,maxn;
{
int ans = 0,op = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') op = -1;
ch = getchar();
}
while(ch >='0' && ch <= '9')
{
ans *= 10;
ans += ch - '0';
ch = getchar();
}
return ans * op;
}

int main()
{
memset(dp1,127/3,sizeof(dp1));
rep(i,1,n)
{
dp1[i][i] = dp1[i+n][i+n] = 0;
}
rep(i,1,n<<1) sum[i] = sum[i-1] + a[i];
rep(j,1,n-1)
{
rep(i,1,(n<<1)-j)
{
rep(k,i,i+j-1)
{
dp1[i][i+j] = min(dp1[i][i+j],dp1[i][k] + dp1[k+1][i+j] + sum[i+j] - sum[i-1]);
dp2[i][i+j] = max(dp2[i][i+j],dp2[i][k] + dp2[k+1][i+j] + sum[i+j] - sum[i-1]);
}
}
}
rep(i,1,n) minn = min(minn,dp1[i][i+n-1]),maxn = max(maxn,dp2[i][i+n-1]);
printf("%d\n%d\n",minn,maxn);
return 0;
}

0
0 收藏

0 评论
0 收藏
0