中国商标官方网站,建筑培训网 江苏,建设网站能赚钱,模板网免费https://www.luogu.org/problemnew/show/P1880 区间dp,顾名思义,是以区间为阶段的一种线性dp的拓展 状态常定义为$f[i][j]$,表示区间[i,j]的某种解; 通常先枚举区间长度,再枚举左端点,最后枚举断点(k) 石子合并便是一道经典的区间dp #include bits/stdc.h
#define read…https://www.luogu.org/problemnew/show/P1880 区间dp,顾名思义,是以区间为阶段的一种线性dp的拓展 状态常定义为$f[i][j]$,表示区间[i,j]的某种解; 通常先枚举区间长度,再枚举左端点,最后枚举断点(k) 石子合并便是一道经典的区间dp #include bits/stdc.h
#define read read()
#define up(i,l,r) for(int i (l);i (r); i)
#define inf 0x3f3f3f3f
using namespace std;
int read
{int x 0;char ch getchar();while(ch 48 || ch 57) ch getchar();while(ch 48 ch 57) {x 10 * x ch - 48; ch getchar();}return x;
}
const int N 205;
int n,cnt[N],sum[N],f1[N][N],f2[N][N];
int main()
{freopen(stone.in,r,stdin);n read;//memset(f2,0x3f,sizeof(f2)); up(i,1,n) cnt[i] cnt[i n] read;//,f1[i][i] 0,f2[i][i] 0; - up(i,1,((n1)-1)) sum[i] sum[i - 1] cnt[i];//前缀和 -[1,2n-1] 处理环; up(L,2,n)//[2,n] //枚举区间长度 up(i,1,( (n1) - L 1) ) //枚举左端点 {int j i L - 1;//右端点; f1[i][j] 0; f2[i][j] inf;//初始化; up(k,i,(j - 1))//枚举断点 [i,j) {f1[i][j] max(f1[i][j],f1[i][k] f1[k 1][j]);f2[i][j] min(f2[i][j],f2[i][k] f2[k 1][j]);}f1[i][j] (sum[j] - sum[i - 1]);f2[i][j] (sum[j] - sum[i - 1]);//!!加上这次合并[i,j]的分数; }int max_ans 0,min_ans inf;up(i,1,n)//[1,n]{int j i n - 1;max_ans max(max_ans,f1[i][j]);min_ans min(min_ans,f2[i][j]);}printf(%d\n,min_ans);printf(%d,max_ans);return 0;
} 转载于:https://www.cnblogs.com/mzg1805/p/10316214.html
