傳送門

文章目錄

• 題意：
• 思路：

題意：

給你$n$個串，字符集是$a?z$，讓你在每個串種選擇一個子序列，保證對于$i<j,s_i<s_j$，也就是選擇的串字典序是嚴格遞增的，讓你選擇一種方式，使得選擇的字符串長度之和最大。

$n\le 15,|s|\le 15$

思路：

其實看到范圍這么小，應該比較容易想到是個狀壓$dp$。

所以我們就套路的設$f[i][j]$表示到了$i$個串，第$i$個串狀態為$j$的方案數，轉移的話就從上一個狀態的所有方案取能到當前串的時候轉移，復雜度$O(n{2}^{30})$，顯然過不去。。。

所以我們考慮優化轉移，注意到直接找字典序不好找，我們能不能維護一個前綴最大值，讓后二分呢？顯然可以，我們改一下狀態，改為$f[i][j]$表示到了第$i$個串，當前選擇的串是第$j$大的串，這樣$n{2}^{15}$預處理一下，讓后轉移$30n{2}^{15}$轉移即可，當然可以優化掉這個二分，由于其具有單調性，整個雙指針即可。

由于一開始看錯題，代碼寫的極其丑陋。

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<deque> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=400100,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n; int f[30][1<<16],g[30][1<<16]; vector<string>s[30];int main() {scanf("%d",&n);for(int i=1;i<=n;i++) {string ss; cin>>ss;int len=ss.length();for(int j=1;j<1<<len;j++) {string now;for(int k=0;k<len;k++) if(j>>k&1) now+=ss[k];s[i].push_back(now);}sort(s[i].begin(),s[i].end()); s[i].erase(unique(s[i].begin(),s[i].end()),s[i].end());}int ans=0;for(int i=1;i<=s[1].size();i++) f[1][i]=s[1][i-1].size(),g[1][i]=max(g[1][i-1],f[1][i]);for(int i=2;i<=n;i++) {int len=s[i].size();for(int j=1;j<=len;j++) {g[i][j]=g[i][j-1];int pos=lower_bound(s[i-1].begin(),s[i-1].end(),s[i][j-1])-s[i-1].begin();if(!pos||!g[i-1][pos]) continue;f[i][j]=g[i-1][pos]+s[i][j-1].size();g[i][j]=max(g[i][j],f[i][j]); // if(i==n&&pos) ans=max(ans,f[i][j]);} // for(int j=1;j<=s[i].size();j++) f[i][j]=s[i][j-1].size(),g[i][j]=max(g[i][j-1],f[i][j]);}ans=g[n][s[n].size()];if(ans==0) puts("-1");else cout<<ans<<endl;return 0; }

總結

以上是生活随笔為你收集整理的2018 ICPC Asia Jakarta Regional Contest J. Future Generation 状压dp的全部內容，希望文章能夠幫你解決所遇到的問題。

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