社区讨论
只能过一个点怎么办,,,
P1880[NOI1995] 石子合并参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mi6h1bw3
- 此快照首次捕获于
- 2025/11/20 04:45 4 个月前
- 此快照最后确认于
- 2025/11/20 04:45 4 个月前
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>//数学函数
#include<string>//字符串
#include<cstdlib>
#include<algorithm>//算法库
#include<vector>//不定长数组
#include<set>//集合
#include<map>//映射
#include<sstream>//字符串流
#include<stack>//栈
#include<iterator>//迭代器
#include<queue>//队列
#include<functional>//函数对象
#include<list>//链表
#include<deque>//双端队列
#include<utility>//pair类型
#include<numeric>//accumulate累加函数
#define N 10005
using namespace std;
const int mod = 1000007;
int a[2005],sum[2005][2005];
int dp1[2005][2005],dp2[2005][2005];
int n,maxx,minn=0x7fffffff;
int main()
{
//freopen("stone3.in","r",stdin);
//freopen("stone3.out","w",stdout);
cin>>n;
for(int i = 1; i <= n; i ++)
{
cin>>a[i]; a[i+n] = a[i];
}
/*for(int p = 1; p <= n-1; p ++)
for(int i = 2; i <= m; i ++)
{
maxx = max( (a[i] + a[i-1]),maxx);
minn = min( (a[i] - a[i-1]),minn);
}*/
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= i+n; j ++)
{
if(i == j) sum[i][j] = a[j];
else
sum[i][j] = sum[i][j-1] + a[j];
}
for(int j = 1; j <= n; j ++)
for(int i = 1; i <= n*2-1; i ++)
for(int k = i; k <= j+i-1; k ++)
{
dp1[i][i+j] = max( dp1[i][i+j], dp1[i][k] + dp1[k+1][i+j] + sum[i][i+j] );
dp2[i][i+j] = min( dp1[i][i+j], dp1[i][k] + dp1[k+1][i+j] + sum[i][i+j] );
}
for(int i = 1; i <= n; i ++)
{
maxx=max(maxx,dp1[i][i+n-1]);
minn=min(minn,dp2[i][i+n-1]);
}
//cout<<maxx;
cout<<minn<<endl<<maxx;
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...