Codeforces Round #622 (Div. 2) D. Happy New Year 状压dp
傳送門
文章目錄
- 題意:
- 思路:
題意:
n≤1e5,m≤1e9,k≤8.n\le 1e5,m\le 1e9,k\le 8.n≤1e5,m≤1e9,k≤8.
思路:
注意到題目中保證了每個(gè)孩子至多收到kkk個(gè),且k≤8k\le 8k≤8,注意到這是題目保證的,并不是說這個(gè)孩子能收到很多,但是收到kkk個(gè)就接受不了別的了,我理解錯(cuò)題意想了一晚上。
看到kkk這么小,自然的想到狀壓了,復(fù)雜度O(n?2k)O(n*2^k)O(n?2k)很完美。
發(fā)現(xiàn)區(qū)間很大,自然想到離散化。通過離散化, 我們可以將其分成若干個(gè)左閉右開的區(qū)間。這個(gè)時(shí)候就可以定義f[i][j]f[i][j]f[i][j]表示選到了第iii個(gè)區(qū)間,且該區(qū)間的狀態(tài)為jjj。jjj是一個(gè)長(zhǎng)度為kkk的二進(jìn)制,某一位iii是111表示第iii條線覆蓋了這個(gè)區(qū)間。由于區(qū)間是左閉右開的區(qū)間,所以左端點(diǎn)才有信息存儲(chǔ),下面分情況討論:
設(shè)當(dāng)前狀態(tài)為jjj,其含有的111的個(gè)數(shù)為cntcntcnt,當(dāng)前這段區(qū)間在第kkk個(gè)。
當(dāng)前需要加上一段區(qū)間:
(1)(1)(1)如果jjj的第k?1k-1k?1位已經(jīng)存在,那么應(yīng)該從前一個(gè)狀態(tài)不含這一位轉(zhuǎn)移過來,即 f[i][j]=f[i?1][jxor1<<k]+len?(cntmod2)f[i][j]=f[i-1][j \ \ xor \ \ 1<<k]+len*(cnt\bmod 2)f[i][j]=f[i?1][j??xor??1<<k]+len?(cntmod2)
(2)(2)(2)如果jjj的第k?1k-1k?1位不存在,那么應(yīng)該從上一個(gè)jjj的狀態(tài)轉(zhuǎn)移,即f[i][j]=f[i?1][j]+len?(cntmod2)f[i][j]=f[i-1][j]+len*(cnt\bmod 2)f[i][j]=f[i?1][j]+len?(cntmod2)
當(dāng)前需要減去一段區(qū)間:
(1)(1)(1)如果jjj的k?1k-1k?1位已經(jīng)存在,由于我們是要?jiǎng)h掉他,所以應(yīng)該將他置為?INF-INF?INF,即f[i][j]=?INFf[i][j]=-INFf[i][j]=?INF。
(2)(2)(2)如果jjj的k?1k-1k?1位不存在,那么從上一個(gè)狀態(tài)的jjj或jxor1<<kj\ \ xor\ \ 1<<kj??xor??1<<k二者大的一個(gè)轉(zhuǎn)移過來,再加上len?(cntmod2)len*(cnt\bmod 2)len?(cntmod2)即可,即f[i][j]=max(f[i?1][j],f[i?1][jxor1<<k])+len?(cntmod2)f[i][j]=max(f[i-1][j],f[i-1][j \ \ xor \ \ 1<<k])+len*(cnt\bmod 2)f[i][j]=max(f[i?1][j],f[i?1][j??xor??1<<k])+len?(cntmod2)。
第一維直接滾動(dòng)一下就好了,或者直接開一維,讓后注意一下遍歷的順序就好啦,具體看代碼吧。
// Problem: D. Happy New Year // Contest: Codeforces - Codeforces Round #622 (Div. 2) // URL: https://codeforces.com/contest/1313/problem/D // Memory Limit: 512 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)//#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<sstream> #include<ctime> #include<cstdlib> #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=400010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;int n,m,k; PII p[N]; vector<int>v; int st[N]; LL f[2][(1<<8)+10];int find(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin(); }int main() { // ios::sync_with_stdio(false); // cin.tie(0);int tot=0,op=0;scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++){int l,r; scanf("%d%d",&l,&r);v.pb(l); v.pb(r+1);p[++tot]={l,i}; p[++tot]={r+1,-i};}//for(int i=1;i<(1<<k);i++) f[0][i]=-INF;memset(f,-0x3f,sizeof(f));f[op][0]=0;sort(p+1,p+1+tot);LL ans=0;for(int i=1;i<=tot;i++) {op^=1;int len=p[i+1].X-p[i].X;if(i==tot) len=0;int id=p[i].Y,pos;if(id>0) {for(int j=0;j<k;j++) if(st[j]==0) { pos=j; st[j]=id; break; }for(int j=0;j<(1<<k);j++)if(j>>pos&1) f[op][j]=f[op^1][j^1<<pos]+len*__builtin_parity(j);else f[op][j]=f[op^1][j]+len*__builtin_parity(j);}else {for(int j=0;j<k;j++) if(st[j]==-id) { pos=j; st[j]=0; break; }for(int j=0;j<(1<<k);j++)if(j>>pos&1) f[op][j]=-INF;else f[op][j]=max(f[op^1][j],f[op^1][j^1<<pos])+len*__builtin_parity(j);}}cout<<f[op][0]<<endl;/*for(int i=1;i<=tot;i++){int len;if(i!=tot) len=p[i+1].X-p[i].X;else len=0;int id=p[i].Y,pos;if(id>0){for(int i=0;i<k;i++) if(st[i]==0) { pos=i; st[i]=id; break; }for(int i=(1<<k)-1;i>=0;i--) if(i>>pos&1) f[i]=f[i^1<<pos]+len*__builtin_parity(i);else f[i]=f[i]+len*__builtin_parity(i);}else {for(int i=0;i<k;i++) if(st[i]==-id) { pos=i; st[i]=0; break; }for(int i=0;i<(1<<k);i++) if(i>>pos&1) f[i]=INF;else f[i]=max(f[i],f[i^1<<pos])+len*__builtin_parity(i);}} printf("%lld\n",f[0]);*/return 0; } /**/總結(jié)
以上是生活随笔為你收集整理的Codeforces Round #622 (Div. 2) D. Happy New Year 状压dp的全部?jī)?nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 电脑不能打字了怎么设置?七点解决问题
- 下一篇: 男子50米自由泳世界记录是多少