# 一个关于序列的游戏——DP综合题()-其他

## 一个关于序列的游戏——DP综合题()

### 题目

1、相邻两个元素相差为1

2、如果某个元素不在连续段的最左或最右，那么这个元素就不能同时小于相邻的左右两个元素。

“1、2、3、4、3” “1、2” “3、2” “3”都符合条件。

### 题解

int get(int l,int r,int k){
if(a[k]+a[k]-a[l]-a[r]+1<0)return -inf;
if(a[k]<a[l]||a[k]<a[r])return -inf;
return up[l,k]+down[k,r]+val[a[k]+a[k]-a[l]-a[r]+1];
}
//在solve中
for(int len=2;len<=n;len++){
for(int l=1,r=len;r<=n;l++,r++){
for(int k=l;k<=r;k++){
f[l][r]=max(f[l][r],get(l,r,k));
if(k<r)f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]);
}
}
}


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 250
#define inf 0x3f3f3f3f
int f[N][N], up[N][N], down[N][N], ans[N][N], n, m, a[N], val[N];
int get(int l, int r, int k) {
if (a[k] + a[k] - a[l] - a[r] + 1 > n)return -inf;
if (a[k] < a[l] || a[k] < a[r])return -inf;
return up[l][k] + down[k][r] + val[a[k] + a[k] - a[l] - a[r] + 1];
}
void init() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> val[i];
for (int i = 1; i <= n; i++)cin >> a[i];
}
//在solve中
void solve() {
memset(f, 0xcf, sizeof f);
memset(up, 0xcf, sizeof f);
memset(down, 0xcf, sizeof f);
for (int i = 1; i <= n; i++)f[i][i - 1] = 0;
f[n + 1][n] = 0;
for (int i = 1; i <= n; i++)up[i][i] = down[i][i] = 0;
for (int len = 0; len <= n; len++) {
for (int l = 1, r = len; r <= n; l++, r++) {
for (int k = l; k <= r; k++) {
f[l][r] = max(f[l][r], get(l, r, k));
if (k < r)f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r]);
}
if (a[l - 1] == a[r + 1] + 1) {
for (int L = 1; L < l; L++) {
for (int R = r + 1; R <= n; R++) {
down[L][R] = max(down[L][R], down[L][l - 1] + f[l][r] + down[r + 1][R]);
}
}
}
if (a[l - 1] == a[r + 1] - 1) {
for (int L = 1; L < l; L++) {
for (int R = r + 1; R <= n; R++) {
up[L][R] = max(up[L][R], up[L][l - 1] + f[l][r] + up[r + 1][R]);
}
}
}
//            printf("%d ", f[l][r]);
}
//        puts("");
}
for (int len = 1; len <= n; len++) {
for (int l = 1, r = len; r <= n; l++, r++) {
ans[l][r] = max(ans[l][r], f[l][r]);
for (int k = l; k < r; k++) {
ans[l][r] = max(ans[l][r], ans[l][k] + ans[k + 1][r]);
}
}
}
}
int main() {
init();
solve();
printf("%d\n", ans[1][n]);
return 0;
}


————————

### 题目

1、相邻两个元素相差为1

2、如果某个元素不在连续段的最左或最右，那么这个元素就不能同时小于相邻的左右两个元素。

“1、2、3、4、3” “1、2” “3、2” “3”都符合条件。

### 题解

int get(int l,int r,int k){
if(a[k]+a[k]-a[l]-a[r]+1<0)return -inf;
if(a[k]<a[l]||a[k]<a[r])return -inf;
return up[l,k]+down[k,r]+val[a[k]+a[k]-a[l]-a[r]+1];
}
//在solve中
for(int len=2;len<=n;len++){
for(int l=1,r=len;r<=n;l++,r++){
for(int k=l;k<=r;k++){
f[l][r]=max(f[l][r],get(l,r,k));
if(k<r)f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]);
}
}
}


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 250
#define inf 0x3f3f3f3f
int f[N][N], up[N][N], down[N][N], ans[N][N], n, m, a[N], val[N];
int get(int l, int r, int k) {
if (a[k] + a[k] - a[l] - a[r] + 1 > n)return -inf;
if (a[k] < a[l] || a[k] < a[r])return -inf;
return up[l][k] + down[k][r] + val[a[k] + a[k] - a[l] - a[r] + 1];
}
void init() {
cin >> n;
for (int i = 1; i <= n; i++)cin >> val[i];
for (int i = 1; i <= n; i++)cin >> a[i];
}
//在solve中
void solve() {
memset(f, 0xcf, sizeof f);
memset(up, 0xcf, sizeof f);
memset(down, 0xcf, sizeof f);
for (int i = 1; i <= n; i++)f[i][i - 1] = 0;
f[n + 1][n] = 0;
for (int i = 1; i <= n; i++)up[i][i] = down[i][i] = 0;
for (int len = 0; len <= n; len++) {
for (int l = 1, r = len; r <= n; l++, r++) {
for (int k = l; k <= r; k++) {
f[l][r] = max(f[l][r], get(l, r, k));
if (k < r)f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r]);
}
if (a[l - 1] == a[r + 1] + 1) {
for (int L = 1; L < l; L++) {
for (int R = r + 1; R <= n; R++) {
down[L][R] = max(down[L][R], down[L][l - 1] + f[l][r] + down[r + 1][R]);
}
}
}
if (a[l - 1] == a[r + 1] - 1) {
for (int L = 1; L < l; L++) {
for (int R = r + 1; R <= n; R++) {
up[L][R] = max(up[L][R], up[L][l - 1] + f[l][r] + up[r + 1][R]);
}
}
}
//            printf("%d ", f[l][r]);
}
//        puts("");
}
for (int len = 1; len <= n; len++) {
for (int l = 1, r = len; r <= n; l++, r++) {
ans[l][r] = max(ans[l][r], f[l][r]);
for (int k = l; k < r; k++) {
ans[l][r] = max(ans[l][r], ans[l][k] + ans[k + 1][r]);
}
}
}
}
int main() {
init();
solve();
printf("%d\n", ans[1][n]);
return 0;
}