題目鏈接

https://atcoder.jp/contests/agc035/tasks/agc035_d

題解

想了兩小時憋出來一個狀壓DP，發現人家怎么空間才十幾MB，原來暴力就行了。。。
考慮原序列那個操作，我們可以建一個圖，一開始有\(n\)個點沒有邊，每次選一個點向其左右未被選的點加兩條邊，一個點的貢獻次數就是它到左右兩個終點的路徑數。
那么我們可以枚舉最后選的點，把原序列分裂成兩個區間，因此使用區間DP. 現在的問題是我們需要方便地統計一個點對總和的貢獻。我們觀察到，從\([l,r]\)這一層到\([1,n]\)最底層，每次要么拓展左邊（左端點\(l\)連向新的\(l'\),\(r\)連向\(l'\)），要么拓展右邊，這樣總共的過程可以表達為一個長度不超過\((n-1)\)的01串，且從\(l\)或\(r\)到達\(1\)或\(n\)的方案數可由這個串得到（具體地，維護兩個變量\(x=1,y=1\), 拓展左邊時\((x,y)\rightarrow (x+y,y)\), 拓展右邊時\((x,y)\rightarrow (x,x+y)\)）。那么預處理每個01串對應的系數，就可以快速計算了。最終的DP狀態是，\(f[l][r][k][S]\)表示區間\([l,r]\)，01串長度為\(k\)，串本身為\(S\).
總共狀態數是\(\sum^n_{i=1}2^i(n-i+1)=O(2^nn)\)的，轉移需要\(O(n)\)的復雜度（其實遠遠不滿），總時間復雜度\(O(2^nn^2)\).
但是如果我們設\(f[l][r][k][S]\)記憶化的話空間復雜度就變成\(O(2^nn^3)\)了，怎么辦？智障的我就把后兩維壓到一起了，卡著空間限制過了……
然而事實是重復遍歷一個狀態的情況很少，不記憶化不僅能過，而且速度還快一倍。（如果不記憶化的話不需要預處理數組，把\(S\)串直接改成左右端點分別被算幾次就行了）
實測效果如下：

（上：不記憶化 下：記憶化）
枯了

代碼

記憶化:

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define riterator reverse_iterator #define U ((1<<n)-1) 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 N = 18; const llong INF = 1e17; llong f[N+1][N+1][(1<<N)+3]; llong val[(1<<N)+3]; llong a[N+3]; int n;void updmin(llong &x,llong y) {x = min(x,y);}llong dfs(int l,int r,int sta) {if(f[l][r][sta]<INF) {return f[l][r][sta];}if(r-l<=1) return f[l][r][sta]=0ll;for(int i=l+1; i<r; i++){updmin(f[l][r][sta],dfs(l,i,((sta<<1)|1)&U)+dfs(i,r,(sta<<1)&U)+a[i]*val[sta]);}return f[l][r][sta]; }int main() {scanf("%d",&n);for(int i=0; i<(1<<n)-1; i++){int len = n; while(i&(1<<len-1)) {len--;} len--;llong x = 1ll,y = 1ll; for(int j=0; j<len; j++) i&(1<<j)?y+=x:x+=y; val[i] = x+y;}for(int i=0; i<n; i++) scanf("%lld",&a[i]);memset(f,10,sizeof(f));printf("%lld\n",dfs(0,n-1,(1<<n)-2)+a[0]+a[n-1]);return 0; }

不記憶化

#include<bits/stdc++.h> #define llong long long #define mkpr make_pair #define riterator reverse_iterator #define U ((1<<n)-1) 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 N = 18; const llong INF = 1e17; llong a[N+3]; int n;void updmin(llong &x,llong y) {x = min(x,y);}llong dfs(int l,int r,llong x,llong y) {if(r-l<=1) return 0ll;llong ret = INF;for(int i=l+1; i<r; i++){updmin(ret,dfs(l,i,x,x+y)+dfs(i,r,x+y,y)+a[i]*(x+y));}return ret; }int main() {scanf("%d",&n);for(int i=0; i<n; i++) scanf("%lld",&a[i]);printf("%lld\n",dfs(0,n-1,1ll,1ll)+a[0]+a[n-1]);return 0; }

總結

以上是生活随笔為你收集整理的AtCoder AGC035D Add and Remove (状压DP)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。