names 排列 fine pac col fin opera print ios
单调队列优化dp;
对于每个点开个单调队列,按转移到它的点到它的距离从大到小,得分也从大到小排列。
每次枚举当前点前面的所有点,对于每个点的队列中二分一个距离小于等于它到当前点的答案值,放到当前点的队列中。
- //Twenty
- #include < algorithm > #include < iostream > #include < cstring > #include < cstdlib > #include < cstdio > #include < vector > #include < cmath > #include < queue > #include < ctime > typedef long long LL;
- using namespace std;
- const int maxn = 1005;
- int n,
- que[maxn][maxn],
- f[maxn][maxn],
- ql[maxn],
- qr[maxn],
- ans = -1e9;
- namespace fastIO {
- const int sz = 1 << 15 | 1;
- char ch,
- buf[sz],
- *l,
- *r;
- void gechar(char & c) {
- if (l == r) r = (l = buf) + fread(buf, 1, sz, stdin);
- c = l == r ? (char) EOF: *l++;
- }
- template < typename T > void read(T & x) {
- int f = 1;
- x = 0;
- gechar(ch);
- while (ch != ‘ - ‘ && (ch < ‘0‘ || ch > ‘9‘)) gechar(ch);
- if (ch == ‘ - ‘) f = -1,
- gechar(ch);
- for (; ch >= ‘0‘ && ch <= ‘9‘; gechar(ch)) x = x * 10 + ch - ‘0‘;
- x *= f;
- }
- }
- struct node {
- int pos,
- v;
- friend bool operator < (const node & A, const node & B) {
- return A.pos < B.pos;
- }
- }
- p[maxn];
- int ef(int i, int lim) {
- int l = ql[i],
- r = qr[i],
- res = -1;
- while (l <= r) {
- int mid = (l + r) >> 1;
- if (que[i][mid] <= lim) res = mid,
- r = mid - 1;
- else l = mid + 1;
- }
- return res;
- }
- void solve() {
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= i - 1; j++) {
- int tp = ef(j, p[i].pos - p[j].pos);
- if (tp != -1) {
- int pp = p[i].pos - p[j].pos,
- vv = f[j][tp] + p[i].v;
- while (ql[i] <= qr[i] && vv >= f[i][qr[i]]) qr[i]--;
- que[i][++qr[i]] = pp;
- f[i][qr[i]] = vv;
- }
- }
- que[i][++qr[i]] = 0;
- f[i][qr[i]] = p[i].v;
- ans = max(ans, f[i][1]);
- }
- }
- void init() {
- fastIO: :read(n);
- for (int i = 1; i <= n; i++) {
- fastIO: :read(p[i].pos);
- fastIO: :read(p[i].v);
- }
- }
- void work() {
- sort(p + 1, p + n + 1);
- for (int i = 1; i <= n; i++) ql[i] = 1,
- qr[i] = 0;
- solve();
- for (int i = 1; i <= n; i++) ql[i] = 1,
- qr[i] = 0;
- for (int i = 1; i <= n; i++) p[i].pos = 1e6 - p[i].pos;
- sort(p + 1, p + n + 1);
- solve();
- printf("%d\n", ans);
- }
- //#define DEBUG
- int main() {#ifdef DEBUG freopen("1.in", "r", stdin);#endif init();
- work();
- return 0;
- }
洛谷 3089 [USACO13NOV]POGO的牛Pogo-Cow
来源: http://www.bubuko.com/infodetail-2369211.html