题解 P3146 【[USACO16OPEN]248】
henry_y
·
·
题解
My\ blogs
写了一个不同于其他题解的dp。
注意到直接枚举转移的话是$O(n^4)$的。考虑优化一下。
因为这样子的dp值是只有0和1的，所以可以拿一个bitset优化一下，就是&一下左右两个子区间然后右移一位就行了。
至于答案可能不需要把整段并起来这个问题，再开一个bitset，每次对得到的区间或以下就好了。
这样就能$O(\frac{n^4}{w})$搞过去了。
```cpp
#include <bits/stdc++.h>
#define ll long long
const ll inf = 1e18;
#define il inline
namespace io {
#define in(a) a = read()
#define out(a) write(a)
#define outn(a) out(a), putchar('\n')
#define I_int ll
inline I_int read() {
I_int x = 0, f = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') f = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
char F[200];
inline void write(I_int x) {
if (x == 0) return (void) (putchar('0'));
I_int tmp = x > 0 ? x : -x;
if (x < 0) putchar('-');
int cnt = 0;
while (tmp > 0) {
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0) putchar(F[--cnt]);
}
#undef I_int
}
using namespace io;
using namespace std;
#define N 310
int n = read();
int a[N];
bitset<1010>f[N][N], ans;
int main() {
for(int i = 1; i <= n; ++i) {
in(a[i]), f[i][i].set(a[i]);
}
for(int len = 1; len <= n; ++len) {
for(int l = 1; l <= n; ++l) {
int r = l + len - 1;
if(r > n) break;
for(int k = l; k < r; ++k) {
f[l][r] |= (f[l][k] & f[k+1][r]) << 1;
ans |= f[l][r];
}
}
}
for(int i = 1009; i; --i) {
if(ans[i] == 1) {
printf("%d\n", i);
return 0;
}
}
}
```