区间dp
常见题型
求区间[1,n]XXXXX后的最大/小值，一般分为无要求或只能/最多分成m段两类
做法
如对分段无要求，设dp[i][j]表示序列中[i,j]的最值，最外层循环区间长度，第二层循环左端点，并能确定右端点，第三层枚举断点；
for(rint len = 1;len <= n; ++len) {//如果对len == 1初始化了可从2枚举
for(rint i = 1,j = i + len - 1;j <= n;++i,++j) {
for(rint k = i;k < j; ++k) {//把序列分成[i,k],[k+1,j];
.......;
}
}
}
环形dp
常见题型
求首尾相接的区间[1,n]XXXXX后的最大/小值；
做法
可拆链转化为区间dp求解
转化方法
对输入的原区间复制一遍接到序列后，则该2n区间任意长为n的区间为原环断开的一种链。
合并石子
非常基础的模板题
#include <iostream>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
#define ll long long
#define rint register int
#define lson (x << 1)
#define rson (x << 1 | 1)
#define mid ((st[x].l + st[x].r) >> 1)
using namespace std;
template <typename xxx>
inline void read(xxx &x) {
x = 0;
int f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-')
f = -1;
c = getchar();
}
while (c <= '9' && c >= '0') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
x *= f;
}
template <typename xxx>
inline void print(xxx x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9)
print(x / 10);
putchar(x % 10 + '0');
}
const int N = 300100;
const int mod = 100003;
const int maxn = 100100;
const int inf = 0x7fffffff;
const int key = 131;
const double eps = 1e-9;
int n;
ll a[444];
ll sum[444];
ll dp[444][444];
ll f[444][444];
int main() {
ll ans=0,fk=1e15;
read(n);
for(rint i=1;i<=n;++i) read(a[i]),a[i+n]=a[i];
for(rint i=1;i<=(n<<1);++i)
{
sum[i]=sum[i-1]+a[i];
for(rint j=i;j<=(n<<1);++j)
if(j^i) f[i][j]=1e15;
}
for(rint len=1;len<n;++len)
{
for(rint i=1;i<=(n<<1);++i)
{
rint j=i+len;
for(rint k=i;k<j;++k)
{
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);
}
}
}
for(rint i=1;i<=n;++i)
{
ans=max(dp[i][i+n-1],ans);
fk=min(f[i][i+n-1],fk);
}
print(fk);putchar('
');print(ans);
}
/*
*/
数字游戏
也是十分基础有限制的基础水题说明我是个水题都做不来的垃圾
有限制的话多开一维dp[i][j][h]表示[i,j]分为h段的最值；最外两层不变，第三层枚举段数h(本题预处理的h == 1所以从2开始)，第四层枚举断点k，范围是[i + h - 1,j - 1];
本题最开始我把sum[]放在初始化dp的双重循环中更新，没有发现初始化需要用到还未更新的sum[],因此错了半天
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <cstring>
#include <algorithm>
#define rint register int
#define ll long long
using namespace std;
template <typename xxx> inline void read(xxx &x)
{
int f = 1;x = 0;
char c = getchar();
for(; c < '0' || c > '9' ; c = getchar()) if(c=='-') f = -1;
for(;'0' <= c && c <= '9'; c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
x *= f;
}
template <typename xxx> inline void print(xxx x)
{
if(x < 0) {
putchar('-');
x = -x;
}
if(x > 9) print(x/10);
putchar(x % 10 + '0');
}
const int inf = 0x7fffffff;
const int maxn = 100100;
const int mod = 1e9+7;
int n,m,n2;
int a[111];
int sum[111];
int f1[111][111][111];// 区间[l,r]分成h段最大
int f2[111][111][111];//最小
inline int deal(int x) {
return (x % 10 + 10) % 10;
}
int main()
{
read(n);read(m);n2 = (n<<1);
for(rint i = 1;i <= n; ++i) {
read(a[i]);
a[i] = (a[i]%10 + 10)%10;
a[i + n] = a[i];
sum[i] = sum[i - 1] + a[i];
}
for(rint i = 1;i <= n; ++i) sum[i + n] = sum[i] + sum[n];
memset(f2,0x3f,sizeof(f2));
for(rint i = 1;i <= n2; ++i)
for(rint j = i;j <= n2; ++j)
f1[i][j][1] = f2[i][j][1] = deal(sum[j] - sum[i - 1]);
for(rint len = 1;len <= n; ++len) {
for(rint i = 1,j = i + len - 1;j <= n2; ++i,++j) {
for(rint h = 2;h <= m; ++h) {
for(rint k = i + h - 2;k < j; ++k) {
f1[i][j][h] = max(f1[i][j][h],f1[i][k][h - 1] * deal(sum[j] - sum[k]));
f2[i][j][h] = min(f2[i][j][h],f2[i][k][h - 1] * deal(sum[j] - sum[k]));
}
}
}
}
int maxx = 0,minn = 0x3f3f3f3f;
for(rint i = 1;i <= n; ++i) {
maxx = max(maxx,f1[i][i + n - 1][m]);
minn = min(minn,f2[i][i + n - 1][m]);
}
print(minn);putchar('
');print(maxx);
}
/*
*/