題目鏈接

https://codeforces.com/contest/1322/problem/D
題面寫得非常模糊，很容易讀錯(cuò)題，建議參考翻譯：https://www.luogu.com.cn/problem/CF1322D

題解

（最大的難點(diǎn)是讀題？讀錯(cuò)題看了一天題解沒看懂的蒟蒻枯了）
考慮假設(shè)沒有選出的 \(l_i\) 不增這個(gè)限制，那么答案是和順序無(wú)關(guān)的，因?yàn)樵谶x出的集合固定后每一位對(duì)答案貢獻(xiàn)的次數(shù)都等于所有小于等于這一位的數(shù)之和除以位權(quán)下取整的值。
那么可以寫出如下 DP: \(f[j][k]\) 表示考慮了第 \(0\) 位至第 \(j\) 位，且恰好有 \(k\) 個(gè)等于第 \(j\) 位 (就相當(dāng)于第 \(j\) 位貢獻(xiàn)為 \(k\))，轉(zhuǎn)移可以枚舉選多少個(gè)。
現(xiàn)在要求選出的 \(l_i\) 不增，那么只需要從后往前掃 (因?yàn)樵瓉?lái)的 DP 也都是從低位轉(zhuǎn)移到高位)，每次刷表即可。\(f[l[i]][k]\) 可以轉(zhuǎn)移到 \(f[l[i]+j][\lfloor\frac{k+1}{2^j}\rfloor]\).
時(shí)間復(fù)雜度按我的實(shí)現(xiàn)應(yīng)該是 \(O((n^2+nm)\log n)\).
哪位神仙教教我 \(O(n^2+nm)\) 的寫法啊 /kel

代碼

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define riterator reverse_iterator #define y1 Lorem_ipsum_dolor using namespace std;inline int read() {int x = 0,f = 1; char ch = getchar();for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}return x*f; }const int mxN = 2e3; int c[mxN+3],a[mxN+3],w[mxN+mxN+3]; int f[mxN+mxN+3][mxN+3]; int mx[mxN+mxN+3]; int n,m;void updmax(int &x,int y) {x = max(x,y);}int main() {n = read(),m = read();for(int i=1; i<=n; i++) c[i] = read();for(int i=1; i<=n; i++) a[i] = read();for(int i=1; i<=n+m; i++) w[i] = read();memset(f,213,sizeof(f));for(int i=1; i<=n+m; i++) f[i][0] = 0;for(int i=n; i>=1; i--){for(int k=mx[c[i]]; k>=0; k--){int tmp = k+1,val = -a[i]+w[c[i]];for(int j=0; tmp; j++,tmp>>=1,val+=w[c[i]+j]*tmp){updmax(mx[c[i]+j],tmp);updmax(f[c[i]+j][tmp],f[c[i]][k]+val);}}for(int j=1; j<=n+m; j++) {updmax(f[j][0],max(f[j-1][0],f[j-1][1]));}}printf("%d\n",f[n+m][0]);return 0; }

總結(jié)

以上是生活随笔為你收集整理的Codeforces 1322D Reality Show (DP)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。