填坑系列(p.302)
既然不知道后面还要卖多少个就加一维状态嘛。。
lrj写的O(n)转移？其实转移可以O(1)
貌似按x排序有奇效？
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream> using namespace std; void setIO(const string& s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
template<typename Q> Q read(Q& x) {
static char c, f;
for(f = ; c = getchar(), !isdigit(c); ) if(c == '-') f = ;
for(x = ; isdigit(c); c = getchar()) x = x * + c - '';
if(f) x = -x;
return x;
}
template<typename Q> Q read() {
static Q x; read(x); return x;
} const int N = + , INF = 0x3f3f3f3f; int p[N], v[N], n, cas;
int f[N][N][N][];
int vis[N][N][N][]; int dfs(int s, int e, int cnt, int pos) {
if(!cnt) return ;
int &ans = f[s][e][cnt][pos];
if(vis[s][e][cnt][pos] == cas) return ans;
vis[s][e][cnt][pos] = cas; ans = -INF;
int a[] = {s, e}; /*for(int i = 0; i < s; i++) {
ans = max(ans, v[i] - cnt * abs(p[i] - p[a[pos]]) + dfs(i, e, cnt - 1, 0));
}
for(int i = e + 1; i < n; i++) {
ans = max(ans, v[i] - cnt * abs(p[i] - p[a[pos]]) + dfs(s, i, cnt - 1, 1));
}*/ if(s - >= ) {
int dlt = cnt * abs(p[s - ] - p[a[pos]]);
ans = max(ans, v[s - ] - dlt + dfs(s - , e, cnt - , ));
ans = max(ans, -dlt + dfs(s - , e, cnt, ));
}
if(e + < n) {
int dlt = cnt * abs(p[e + ] - p[a[pos]]);
ans = max(ans, v[e + ] - dlt + dfs(s, e + , cnt - , ));
ans = max(ans, -dlt + dfs(s, e + , cnt, )) ;
} return ans;
} int main() {
#ifdef DEBUG
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif int T; scanf("%d", &T);
for(cas = ; cas <= T; cas++) {
scanf("%d", &n);
for(int i = ; i < n; i++) scanf("%d", p + i);
for(int i = ; i < n; i++) scanf("%d", v + i); int ans = ;
for(int k = ; k <= n; k++) {
for(int i = ; i < n; i++) {
ans = max(ans, v[i] - k * abs(p[i]) + dfs(i, i, k - , ));
}
}
printf("%d\n", ans);
} return ;
}