? ? ? ?我分到的任務是看ppt……so這篇blog大概就是我的任務進度了？好像還混雜了一些奇怪的求助……

?

提綱篇

又名如何高效看PPT？

?

動態(tài)規(guī)劃優(yōu)化.pdf? By ExfJoe

2018/4/11?14:09?

第一部分，講了講DP的定義……道理我都懂……

?

第二部分講模型，還是沒有題
計數(shù)類DP 矩陣、斯特林數(shù)，用恰好為k、大于等于k等限制來描述
期望類DP 期望的線性性，迭代法和消元，注意概率獨立

?

第三部分講優(yōu)化
各種優(yōu)化要滿足的條件都是用數(shù)學公式給出的，比較整齊好記
不過還是那句話——道理我都懂啊？？？
滾動數(shù)組、隊列過濾（像插頭DP把有用狀態(tài)放hash表里什么的）
前后綴、決策單調(diào)性（$w[i][j]+w[i+1][j+1]<=w[i+1][j]+w[i][j+1]$）
單調(diào)隊列、斜率優(yōu)化（斜率和橫坐標都遞增可以單隊做到O(n)，否則CDQ或平衡樹）
矩陣、遞推（多項式求逆，簡單提了一句特征多項式；式子構造得蜜汁奇怪，不過在zzh的援助下大致知道了應該怎么處理它？）
容斥原理（+-1、組合數(shù)、帶mu容斥就是反演的式子，P40有個關于補集的式子）

?

第四部分開始講題了，沒有部分分的樣子……
124一眼題，3也挺簡單，56中等題
78910都比較好
有一種目標明確地去做DP題比考場上碰到DP分析出來再去找狀態(tài)容易得多的錯覺……

?

emmm……總結？
概念部分沒什么用……
如果想看題就從第5題開始吧，pdf上的題面和講解都還不錯
其實應該看著pdf完成想題和解題的過程……所以提綱部分先不寫題解啦
我去寫了的題應該會另外寫題解？這只是個針對pdf的總結
我沒看懂的部分是P62-65、P76-78的題解，需要隊友幫助……
5是hihocoder challenge19 A
6是HDU4809，感覺會了思路之后實現(xiàn)不會特別困難
7是TopCoder SRM641 Hard 加強版？？？懷疑這題不存在于這個pdf以外的地方
8是Codeforces 722E 從特殊到一般的過程
9是Codechef SEP11 CNTHEX 有點妙啊……意外好像又在情理之中
10……作者寫了unknown但是zzh指出它是BZOJ4712

這個pdf我已經(jīng)寫了的題有3568，打算去寫910

我為啥一開始就開了個1000多k的pdf……

?

?

?動態(tài)規(guī)劃.ppt? By alpq654321

2018/4/12 09:15

Part1 經(jīng)典題的擴展

lis問題？$n^2$->$nlogn$。

$exp$：給出兩個序列，可以有限次用另一個序列對應位置替換這個序列呢（Bestcoder#20 magic balls）？多來幾個樹狀數(shù)組就行了嘛。

$exp^2$：同時交換兩個序列中某些元素的位置，每次詢問像上面那樣無限次替換后能否嚴格遞增（BZOJ3526 POI2014 Card）？線段樹區(qū)間合并，$s[i][1/0][1/0]$表示區(qū)間$i$左邊換不換/右邊換不換能否嚴格遞增，修改就相當于兩個單點賦值重新pushup一遍就可以了……這東西脫離DP本質(zhì)了……不過Lis本身也只是個定義未必要用DP解決啊。

$exp^3$：把一個排列從小到大依次插入每次詢問lis（BZOJ3173 TJOI2013最長上升子序列）？智障題，平衡樹維護出來最后序列再樹狀數(shù)組一波就行了嘛。

$exp^4$：給十進制數(shù)按位求lis，問區(qū)間里lis恰好為$k$的數(shù)的個數(shù)呢？數(shù)位DP套數(shù)位DP，$f[i][j]$表示到第$i$位而lis狀態(tài)為$j$的方案數(shù)，$j$本來是$10^{10}$但是它不降且最多大1就可以用二進制表示變成$2^{10}$了。盡管做過這種套路的題目還是覺得挺有意思的。

$exp^5$：給出lis求方案數(shù)（BZOJ3591 最長上升子序列）？省選模擬賽原題arg，然而我TLE了？？？反正思路就是三進制表示，不去卡常了。

01背包問題？$nm$

$exp$：每次詢問刪去物品$i$最大容量為$j$的背包（BZOJ3163 HEOI2013Eden的新背包問題）？低配的消失之物。配置太低以至于可以算每個物品前/后的背包并起來……會做《消失之物》何必用這種方法呢……

$exp^2$：BZOJ2287 POJ Challenge 消失之物？經(jīng)典題，無需多言。

比起lis這些exp很讓人失望啊……

?

Part2 基于位運算的DP問題

并不是狀壓和插頭……是按位考慮啦。

BZOJ3668 NOI2014起床困難綜合癥：就是個貪心，大家都會。

BZOJ4069 APIO2015巴厘島的雕塑：必須使用數(shù)據(jù)分治，除此之外挺可做的。

51nod 子集價值：新定義位運算求所有子集運算結果的平方和……去寫的過程中偶然發(fā)現(xiàn)出題人就是ppt作者……好吧好吧。

HDU5270 ZYB loves XOR 2：是原來做Atcoder時做過的題加強版……當時沒寫，現(xiàn)在因為它不是DP可能仍然不會寫。

這部分難道不是只有T2的后一半和T3是DP嗎……亂分類差評。

?

Part3 動態(tài)規(guī)劃中的剪枝

T1據(jù)說是Bestcoder Round#30的D，但是BC好像沒有Round#30……#29和#31之間有一個Valentine's Day Round，它的D看起來并不像啊。并且P38講的優(yōu)化沒有看懂，因為不知道是怎么轉(zhuǎn)化成矩形的，這和前面的講解好像有點不一樣……

Topcoder SRM 639Div1-Level 2：神奇的逐步優(yōu)化，需要認真觀察性質(zhì)，比較值得寫

Topcoder SRM 547Div1-Level 3：聞所未聞……首先DP就很神，還有卡常教程……講這題的P44-P50幾乎全沒看懂

?

總結……

lis的exp^2和exp^4還有點意思。

巴厘島的雕塑可以稍微看一下思路……自己想也能想出來。?

Part2的后兩題和Part3的三道題都挺不錯的。

這個ppt我寫了Part2的23，還打算去寫Part2的4

這么說我現(xiàn)在把超過1000k的兩個ppt都看完啦……望天……還有辣么多（因為只有題目沒有題解才）幾百k的ppt。

?

?

?

題解篇

大概是ppt里我去寫了的題……從某種角度來講DP專題治好了我的計數(shù)恐懼癥。

?

CF590D

? ? ? ? 看起來沒有那么水實際上真心水的題。題目限制最多交換$s$次，實際上最多$n*(n-1)/2$次是有用的，所以$f[i][j][l]$表示到第$i$個數(shù)選了$j$個數(shù)交換了$l$次的最優(yōu)解，枚舉每個數(shù)選還是不選來轉(zhuǎn)移，第一維顯然可以滾動。如果把$s$看成$n^2$，時間復雜度$n^4$，空間復雜度$n^3$。

cf590D

?

HDU4809

? ? ? ? 想起來比上一題稍微有難度一點。首先三個人的限制是沒用的，可以直接求一個人的再乘三。然后定義狀態(tài)數(shù)組$f[i][j][0/1/2]$表示以$i$為根的子樹$X-Y$的值為$j$不選擇$i$/$i$所在聯(lián)通塊有奇數(shù)個點/$i$所在聯(lián)通塊有偶數(shù)個點的方案數(shù)，注意這里的$j$是不把$i$所在聯(lián)通塊計算進去的。有了狀態(tài)定義之后轉(zhuǎn)移十分容易，就是把兒子向父親合并的過程。需要注意的就是兒子合并后父親原來的狀態(tài)都不再存在了，所以應該用合并后的DP值取代原來的而不是把它累加上去；以及初始化$f[i][0][1]=1$,$f[i][0][0]=2$，因為不選的點可能被另外兩個人選。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define ll long long 5 using namespace std; 6 const int sj=310; 7 const int bd=305; 8 const int mod=1e9+7; 9 int n,h[sj],e,l[sj],r[sj],tp; 10 ll f[sj][sj<<1][3],tmp[sj<<1][3],ans; 11 struct B 12 { 13 int ne,v; 14 }b[sj<<1]; 15 void add(int x,int y) 16 { 17 b[e].v=y,b[e].ne=h[x],h[x]=e++; 18 b[e].v=x,b[e].ne=h[y],h[y]=e++; 19 } 20 inline int read() 21 { 22 int jg=0,jk=getchar()-'0'; 23 while(jk<0||jk>9) jk=getchar()-'0'; 24 while(jk>=0&&jk<=9) jg*=10,jg+=jk,jk=getchar()-'0'; 25 return jg; 26 } 27 void dfs(int x,int fx) 28 { 29 f[x][bd][1]=1,f[x][bd][0]=2; 30 l[x]=r[x]=0; 31 for(int i=h[x];i!=-1;i=b[i].ne) 32 if(b[i].v!=fx) 33 { 34 dfs(b[i].v,x),tp=b[i].v; 35 memset(tmp,0,sizeof(tmp)); 36 for(int j=l[x];j<=r[x];j++) 37 for(int k=l[tp]-1;k<=r[tp]+1;k++) 38 { 39 if(j+k<-n||j+k>n) continue; 40 tmp[j+bd+k][0]=(tmp[j+bd+k][0]+f[x][j+bd][0]*f[tp][k+bd][0]+f[x][j+bd][0]*f[tp][k+bd-1][1]+f[x][j+bd][0]*f[tp][k+bd+1][2])%mod; 41 tmp[j+bd+k][1]=(tmp[j+bd+k][1]+f[x][j+bd][1]*f[tp][k+bd][0]+f[x][j+bd][2]*f[tp][k+bd][1]+f[x][j+bd][1]*f[tp][k+bd][2])%mod; 42 tmp[j+bd+k][2]=(tmp[j+bd+k][2]+f[x][j+bd][2]*f[tp][k+bd][0]+f[x][j+bd][1]*f[tp][k+bd][1]+f[x][j+bd][2]*f[tp][k+bd][2])%mod; 43 if(tmp[j+k+bd][0]||tmp[j+k+bd][1]||tmp[j+k+bd][2]) 44 { 45 if(l[x]>j+k) l[x]=j+k; 46 if(r[x]<j+k) r[x]=j+k; 47 } 48 } 49 for(int j=l[x];j<=r[x];j++) 50 memcpy(f[x][j+bd],tmp[j+bd],sizeof(tmp[j+bd])); 51 } 52 } 53 int main() 54 { 55 while(scanf("%d",&n)!=EOF) 56 { 57 memset(h,-1,sizeof(h)); 58 memset(f,0,sizeof(f)); 59 ans=e=0; 60 for(int i=1;i<n;i++) add(read(),read()); 61 dfs(1,0); 62 for(int i=bd+1;i<=bd+n;i++) 63 ans=(ans+(i-bd)*(f[1][i][0]+f[1][i-1][1]+f[1][i+1][2]))%mod; 64 ans=ans*3%mod; 65 printf("%lld\n",ans); 66 } 67 return 0; 68 } hdu4809

?

CF722E

? ? ? ??其實是某NOIP模擬題的高配版本……分析題目可以發(fā)現(xiàn)經(jīng)過超過$logs$個特殊點時對答案的貢獻都是1，所以只要統(tǒng)計只經(jīng)過0～$logs$的方案即可，經(jīng)過0個特殊點的方案就是NOIP模擬題。當時的做法是$f[i]$表示只經(jīng)過第$i$個點的方案數(shù)，然后$f[i]=C(x_i+y_i,x_i)-\sum_{j=1}^{i-1}{f[j]*C(x_i-x_j+y_i-y_j,x_i-x_j)}$。把這種思路推廣到多個點，用$f[i][j]$表示第$j$個經(jīng)過$i$的方案數(shù)，簡單地容斥一下$f[i][j]=C(x_i+y_i,x_i)-\sum_{l=1}^{i-1}{f[l][j]*C(x_i-x_l+y_i-y_l,x_i-x_l)}-\sum_{l=1}^{j-1}{f[i][l]}$，總復雜度$n^2logs$。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #define ll long long 7 using namespace std; 8 inline int read() 9 { 10 int jg=0,jk=getchar()-'0'; 11 while(jk<0||jk>9) jk=getchar()-'0'; 12 while(jk>=0&&jk<=9) jg*=10,jg+=jk,jk=getchar()-'0'; 13 return jg; 14 } 15 const int mod=1e9+7; 16 const int sj=200010; 17 ll fac[sj],inv[sj],f[2010][25],all,ans; 18 int n,m,k,s,bin[25],vl[25],top,mx; 19 struct point 20 { 21 int xa,ya; 22 }p[2010]; 23 int comp(const point&x,const point&y) 24 { 25 return (x.xa==y.xa)?(x.ya<y.ya):(x.xa<y.xa); 26 } 27 ll ksm(ll x,int y) 28 { 29 ll ret=1; 30 while(y) 31 { 32 if(y&1) ret=ret*x%mod; 33 x=x*x%mod,y>>=1; 34 } 35 return ret; 36 } 37 inline ll c(int x,int y) 38 { 39 return fac[x]*inv[y]%mod*inv[x-y]%mod; 40 } 41 int main() 42 { 43 n=read(),m=read(),k=read(),s=read(); 44 for(int i=1;i<=k;i++) p[i].xa=read(),p[i].ya=read(); 45 sort(p+1,p+k+1,comp); 46 p[++k].xa=n,p[k].ya=m; 47 bin[0]=fac[0]=1,vl[0]=s; 48 for(int i=1;i<=20;i++) 49 { 50 bin[i]=bin[i-1]<<1,vl[i]=ceil((double)s/bin[i]); 51 if(vl[i]==1&&!top) top=i; 52 } 53 mx=n+m; 54 for(int i=1;i<=mx;i++) fac[i]=fac[i-1]*i%mod; 55 inv[mx]=ksm(fac[mx],mod-2); 56 for(int i=mx;i>=1;i--) inv[i-1]=inv[i]*i%mod; 57 for(int i=1;i<=k;i++) 58 for(int j=1;j<=top;j++) 59 { 60 f[i][j]=c(p[i].xa+p[i].ya-2,p[i].ya-1); 61 for(int l=1;l<i;l++) 62 if(p[l].ya<=p[i].ya) 63 f[i][j]=(f[i][j]-f[l][j]*c(p[i].ya-p[l].ya+p[i].xa-p[l].xa,p[i].xa-p[l].xa)%mod+mod)%mod; 64 for(int l=1;l<j;l++) 65 f[i][j]=(f[i][j]-f[i][l]+mod)%mod; 66 } 67 all=c(n+m-2,n-1); 68 for(int j=1;j<=top;j++) 69 { 70 all=(all-f[k][j]+mod)%mod; 71 ans=(ans+vl[j-1]*f[k][j])%mod; 72 } 73 ans=(ans+all)%mod; 74 ans=ans*ksm(c(n+m-2,n-1),mod-2)%mod; 75 printf("%I64d",ans); 76 return 0; 77 } cf722E

?

hihoCoder challenge 19A/1279

? ? ? ? 吉老師的題……比較顯然的思路是$f[i][j][k]$表示選到第$i$個數(shù)異或和為$j$與為$k$的方案數(shù)，但是這樣復雜度是$n*4^{13}$，時間空間都很難接受。

? ? ? 考慮一下與運算的性質(zhì)，只要有一個0它就為0，那我們只需要知道這一位有沒有出現(xiàn)過0就好了。可以用一個二進制數(shù)來記錄每一位是否有0，為了求異或還需要知道每一位1的個數(shù)和01總個數(shù)的奇偶性。假設異或和為$x$，與為$y$，如果有奇數(shù)個數(shù)則$x$&$y=y$，否則$x$&$y=0$。現(xiàn)在定義$xx$表示$x$去掉所有位都為1的部分，那么合法的$x$必須滿足$xx$是$y$的補集的子集，所有合法的$xx$與$y$都可以通過枚舉$y$再枚舉子集預處理出來，給每個數(shù)對編號并存下對應的$xx$和$y$，共有$3^{13}$種合法數(shù)對。如果我們有$xx$和$y$，奇數(shù)時$x=xx|y$，偶數(shù)時$x=xx$；如果我們有$x$和$y$，$xx=x$&(~$y$)。現(xiàn)在定義狀態(tài)數(shù)組$f[i][j][0/1]$表示到了第$i$位$xx$和$y$組合的編號為$j$，選了偶數(shù)/奇數(shù)個數(shù)的方案數(shù)，通過$xx$和$y$還原出$x$、$y$進行操作再得到新的$xx$和$y$來轉(zhuǎn)移。初始化什么都沒選，$xx$為0而$y$為全集；統(tǒng)計答案時只有兩種情況合法：選了奇數(shù)個數(shù)并且$xx$為0、選了偶數(shù)個數(shù)并且$xx$、$y$均為0。需要滾動數(shù)組，時間復雜度$n*2*3^{13}$。

? ? ? ?回顧一下這道題，之所以要引入$xx$就是因為它和$y$之間有特殊關系，可以快速預處理得到，并且能通過它和$y$去還原出$x$。一個數(shù)位全部都是1在這道題里算一個很特殊的情況，所以針對特殊情況設計算法是主要突破口；通過新定義獲取有用狀態(tài)優(yōu)化時間和空間復雜度是最大的亮點。

UPD：感覺……上面那些全是……實際上暴力轉(zhuǎn)移用hash表實現(xiàn)，寫得漂亮一點可過？？？這樣看起來問題的關鍵就只有分析出合法狀態(tài)很少了……除此之外還可以枚舉最后的與，每次DP一遍求異或等于它的方案數(shù)，因為去掉為1的位后異或是與的補集的子集，復雜度也是$n*3^{13}$；不過最后與為0的部分需要容斥，細節(jié)聽起來會多一點。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define ll long long 5 using namespace std; 6 inline int read() 7 { 8 int jg=0,jk=getchar()-'0'; 9 while(jk<0||jk>9) jk=getchar()-'0'; 10 while(jk>=0&&jk<=9) jg*=10,jg+=jk,jk=getchar()-'0'; 11 return jg; 12 } 13 const int sj=1594323; 14 int n,a[55],cnt,id[8192][8192],nt,la,an[sj],xo[sj],tx,ty; 15 ll f[2][sj][2],ans; 16 void pre() 17 { 18 for(int i=0,j;i<8192;i++) 19 { 20 j=(~i)&8191; 21 for(int k=j;;k=(k-1)&j) 22 { 23 an[cnt]=i,xo[cnt]=k; 24 id[i][k]=cnt++; 25 if(!k) break; 26 } 27 } 28 } 29 int main() 30 { 31 n=read(); 32 for(int i=1;i<=n;i++) a[i]=read(); 33 pre(); 34 f[0][id[8191][0]][0]=1; 35 for(int i=1;i<=n;i++) 36 { 37 nt=i&1,la=nt^1; 38 for(int j=0;j<cnt;j++) 39 memcpy(f[nt][j],f[la][j],sizeof(f[nt][j])); 40 for(int j=0;j<cnt;j++) 41 for(int k=0;k<=1;k++) 42 { 43 if(!f[la][j][k]) continue; 44 tx=xo[j],ty=an[j]; 45 if(k) tx|=ty; 46 tx^=a[i],ty&=a[i]; 47 tx&=(~ty); 48 f[nt][id[ty][tx]][k^1]+=f[la][j][k]; 49 } 50 } 51 ans=f[nt][id[0][0]][0]; 52 for(int i=1;i<cnt;i++) 53 if(xo[i]==0) 54 ans+=f[nt][i][1]; 55 printf("%lld",ans); 56 return 0; 57 } hihocoder1279 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define ll long long 5 using namespace std; 6 const int sj=55; 7 const int mod=2332333; 8 int n,a[sj],bin[sj],nt,la,a1,a2,tot; 9 ll ans; 10 struct hash_table 11 { 12 struct B 13 { 14 int ne,v; 15 ll w; 16 }b[1594323]; 17 int h[mod],e; 18 inline void clear() 19 { memset(h,-1,sizeof(h));e=0; } 20 inline ll &operator [] (int x) 21 { 22 for(int i=h[x%mod];i!=-1;i=b[i].ne) 23 if(b[i].v==x) return b[i].w; 24 b[e].v=x,b[e].w=0,b[e].ne=h[x%mod],h[x%mod]=e++; 25 return b[e-1].w; 26 } 27 }f[2]; 28 int main() 29 { 30 scanf("%d",&n); 31 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 32 bin[0]=1; 33 for(int i=1;i<=26;i++) bin[i]=bin[i-1]<<1; 34 tot=bin[13]-1; 35 f[0].clear(); 36 for(int i=1;i<=n;i++) 37 { 38 nt=i&1,la=nt^1; 39 f[nt]=f[la]; 40 a1=a[i]+(a[i]<<13); 41 f[nt][a1]++; 42 for(int j=0;j<f[la].e;j++) 43 { 44 a1=f[la].b[j].v&tot,a2=f[la].b[j].v>>13; 45 a1&=a[i],a2^=a[i]; 46 a1+=a2<<13; 47 f[nt][a1]+=f[la].b[j].w; 48 } 49 } 50 for(int j=0;j<f[nt].e;j++) 51 { 52 a1=f[nt].b[j].v&tot,a2=f[nt].b[j].v>>13; 53 if(a1==a2) ans+=f[nt].b[j].w; 54 } 55 printf("%lld",ans); 56 return 0; 57 } hash_table

?

APIO2015 巴厘島的雕塑

? ? ? ? 清新小水題，除了數(shù)據(jù)分治這點算是非常規(guī)操作，然而兩部分思路相近也都很好寫不算難以接受。先考慮前四個subtask滿足$n<=100$，從高位到低位貪心地看這一位能否為1，用$f[i][j]$表示到$i$分了$j$組是否能使這一位不出現(xiàn)1。假設我們正在處理第$l$位，從$f[k][j-1]$轉(zhuǎn)移到$f[i][j]$需要滿足$f[k][j-1]==1$&&$(sum[i]-sum[k])$&$bin[i]$==0&&$(((sum[i]-sum[k])|ans)>>i)==(ans>>i)$，如果最后$f[n][a]$~$f[n][b]$里有合法的則這一位可以為0。對于最后一個$n<=2000$的subtask組數(shù)沒有下界，可以用$g[i]$表示到$i$最少分多少組可以不出現(xiàn)1，轉(zhuǎn)移方式基本同上，最后只要比較$g[n]$與$B$的大小關系就可以知道這一位能否為0了。WA了兩發(fā)因為沒考慮到單個值不炸int前綴和就炸了，二進制數(shù)位沒開夠……

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define ll long long 5 using namespace std; 6 const int sj=2010; 7 int n,a,b,v[sj],g[sj]; 8 ll sum[sj],ans,bin[50]; 9 bool op,f[105][105]; 10 inline int read() 11 { 12 int jg=0,jk=getchar()-'0'; 13 while(jk<0||jk>9) jk=getchar()-'0'; 14 while(jk>=0&&jk<=9) jg*=10,jg+=jk,jk=getchar()-'0'; 15 return jg; 16 } 17 void work1() 18 { 19 for(int i=49;i>=0;i--) 20 { 21 memset(f,0,sizeof(f)); 22 f[0][0]=1,op=0; 23 for(int j=1;j<=b;j++) 24 for(int k=1;k<=n;k++) 25 for(int l=0;l<k;l++) 26 if(f[l][j-1]&&((sum[k]-sum[l])&bin[i])==0&&(((sum[k]-sum[l])|ans)>>i)==(ans>>i)) 27 f[k][j]=1; 28 for(int j=a;j<=b;j++) 29 if(f[n][j]) 30 { op=1;break; } 31 if(!op) ans+=bin[i]; 32 } 33 printf("%lld",ans); 34 } 35 void work2() 36 { 37 for(int i=49;i>=0;i--) 38 { 39 memset(g,0x3f,sizeof(g)); 40 g[0]=0; 41 for(int j=1;j<=n;j++) 42 for(int k=0;k<j;k++) 43 if(g[k]+1<g[j]&&((sum[j]-sum[k])&bin[i])==0&&(((sum[j]-sum[k])|ans)>>i)==(ans>>i)) 44 g[j]=g[k]+1; 45 if(g[n]>b) ans+=bin[i]; 46 } 47 printf("%lld",ans); 48 } 49 int main() 50 { 51 n=read(),a=read(),b=read(); 52 for(int i=1;i<=n;i++) 53 v[i]=read(),sum[i]=sum[i-1]+v[i]; 54 bin[0]=1; 55 for(int i=1;i<50;i++) bin[i]=bin[i-1]<<1; 56 if(n<=100) work1(); 57 else work2(); 58 return 0; 59 } sculpture

?

51nod 子集價值

? ? ? ? 如果所求不是平方和的話思路非常好想，統(tǒng)計第$j$位時用$f[i][0/1]$表示到第$i$個數(shù)為0/1的方案數(shù)，最后用$ans=\sum{bin[j]*f[n][1]}$。現(xiàn)在我們所求是平方和，可以把平方拆開，假設最后得到的數(shù)$x$二進制表示為$a_1+a_2+a_3$，$x^2=a_1^2+a_2^2+a_3^2+2*a_1*a_2+2*a_1*a_3+2*a_2*a_3$，平方項其實也可以看成同一位的兩個$a_i$相乘，那么對于每兩位$i$、$j$對答案的貢獻都為$i$、$j$同時為1的方案數(shù)$×2^{i+j}$。所以枚舉每兩位，用$f[i][0/1][0/1]$表示到第$i$個數(shù)這兩位分別為0/1的方案數(shù)。實現(xiàn)上要注意初始化問題，我剛開始初始化$f[0][0][0]=1$，但是這樣并不能準確地表達出“選取子集”的含義（相當于空集一直在狀態(tài)里，但它本身不合法）；正確的方法是在DP到第$k$個數(shù)時假設$b_k$的兩個二進制位分別為$d$、$q$，$f[k][d][q]++$，這樣就能表示從當前位開始選取了。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define ll long long 5 using namespace std; 6 const int sj=50010; 7 const int mod=1e9+7; 8 int n,p,a[2][2],b[sj],bin[30],f[sj][2],g[sj][2][2]; 9 ll ans; 10 bool d,q; 11 inline int read() 12 { 13 int jg=0,jk=getchar()-'0'; 14 while(jk<0||jk>9) jk=getchar()-'0'; 15 while(jk>=0&&jk<=9) jg*=10,jg+=jk,jk=getchar()-'0'; 16 return jg; 17 } 18 int main() 19 { 20 n=read(),p=read(); 21 for(int i=0;i<=1;i++) 22 for(int j=0;j<=1;j++) 23 a[i][j]=read(); 24 for(int i=1;i<=n;i++) b[i]=read(); 25 bin[0]=1; 26 for(int i=1;i<p;i++) bin[i]=bin[i-1]<<1; 27 for(int i=0;i<p;i++) 28 for(int j=0;j<p;j++) 29 { 30 memset(g[0],0,sizeof(g[0])); 31 for(int k=1;k<=n;k++) 32 { 33 memcpy(g[k],g[k-1],sizeof(g[k])); 34 d=b[k]&bin[i],q=b[k]&bin[j]; 35 g[k][d][q]=(g[k][d][q]+1)%mod; 36 for(int l=0;l<=1;l++) 37 for(int z=0;z<=1;z++) 38 g[k][a[l][d]][a[z][q]]=(g[k][a[l][d]][a[z][q]]+g[k-1][l][z])%mod; 39 } 40 ans=(ans+1ll*bin[i]*bin[j]%mod*g[n][1][1])%mod; 41 } 42 printf("%lld",ans); 43 return 0; 44 } value

?

?

?

交流篇

一群毒瘤換題做……

?

CF418D 戀愛循環(huán)

? ? ? ? 詢問數(shù)太多了顯然要預處理。對于每一個字母$k$單獨統(tǒng)計，$f[i][j]$表示從$i$到$j$中$k$的個數(shù)，$g[k][j]$表示字母$k$替換$j$個位置的最長長度。一邊統(tǒng)計$f[i][j]$一邊更新$g[k][j-i+1-f[i][j]]$，最后別忘了$g[k]$要取前綴最大。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int sj=1510; 6 int n,q,m,f[sj][sj],g[26][sj],nt,la; 7 char s[sj],p[4]; 8 inline int read() 9 { 10 int jg=0,jk=getchar()-'0'; 11 while(jk<0||jk>9) jk=getchar()-'0'; 12 while(jk>=0&&jk<=9) jg*=10,jg+=jk,jk=getchar()-'0'; 13 return jg; 14 } 15 inline void maxx(int &x,int y) 16 { 17 x=x>y?x:y; 18 } 19 int main() 20 { 21 n=read(); 22 scanf("%s",s+1); 23 q=read(); 24 for(int k=0;k<26;k++) 25 { 26 memset(f,0,sizeof(f)); 27 for(int i=1;i<=n;i++) 28 for(int j=i;j<=n;j++) 29 { 30 f[i][j]=f[i][j-1]; 31 if(s[j]-'a'==k) f[i][j]++; 32 maxx(g[k][j-i+1-f[i][j]],j-i+1); 33 } 34 for(int i=1;i<=n;i++) 35 maxx(g[k][i],g[k][i-1]); 36 } 37 for(int i=1;i<=q;i++) 38 { 39 m=read(); 40 scanf("%s",p); 41 printf("%d\n",g[p[0]-'a'][m]); 42 } 43 return 0; 44 } love

?

LR#6 花火

? ? ? ??把我從0or100中拯救出來的有部分分的好題，這才叫OI嘛。前兩個subtask據(jù)說可以暴搜，DFS有6分BFS有17分，然而我BFS了一發(fā)沒hash記憶化MLE了只拿了6分……

? ? ? ?之后的多項式復雜度算法需要分析一些結論。首先在什么時候交換兩個不相鄰元素是沒有關系的，所以可以一開始就枚舉交換點。其次交換相鄰元素的次數(shù)等于逆序?qū)?shù)，這個稍微想一想還是很好理解的，只要是逆序早晚需要交換它們一次且只用交換一次。提到逆序?qū)ξ覀兙秃苡兄v頭了，在$n^2$枚舉最開始交換哪兩個元素的基礎上逐步優(yōu)化。subtask3的16分允許$n^2$暴力求逆序?qū)?#xff0c;subtask4的8分用$nlog$求逆序?qū)Φ奶茁肪涂梢越鉀Q。再分析一下每次只在原序列基礎上動兩個元素，可以只求出這兩個元素對逆序?qū)Φ挠绊?#xff0c;主席樹隨便維護一下權值。如果用“假裝把它們刪掉再換位插回去”的思路要在主席樹里查很多次只能過subtask5，分析一下只有兩點中間權值落在兩個修改點中間的元素會影響答案就可以只查一次過掉subtask6。現(xiàn)在求逆序?qū)Σ糠值膹碗s度就只有$log$了，到$n^2logn$為止能拿到61分。如果不用數(shù)據(jù)結構直接維護二維前綴和可以直接$O(1)$求出變化后的逆序?qū)?shù)通過subtask7……數(shù)據(jù)結構就算好寫也不要貿(mào)然去打啊。

? ? ? ? 從現(xiàn)在開始邁上通往AC的道路……實際上好像已經(jīng)到了。把下標看作$x$軸權值看作$y$軸，我們是在找一個以兩點分別為左上角和右下角、包含點最多的矩形——這不就是省選模擬題《圈草地》嗎？大致就是左上角、右下角的最優(yōu)點縱坐標一定都是單調(diào)的，所以把所有點分成左上方、右下方和中間三種并用ABC表示。用線段樹維護每個A類點右下方的權值，按橫坐標從小到大掃所有點。碰到A類點就把它的位置初始化，碰到B類點把它上方A的權值+1；碰到C類點把它下方的B類點刪去并消掉貢獻，再查詢它上方A類點的最大權值。B類點可以用set維護，總復雜度$nlogn$。

? ? ? ?感覺我又被騙來做了一道不像DP的題……從頭到尾這哪DP了這。

1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define ll long long 5 using namespace std; 6 const int sj=300010; 7 int n,a[sj],rt[sj],cnt; 8 ll tp,nt,ans; 9 inline int read() 10 { 11 int jg=0,jk=getchar()-'0'; 12 while(jk<0||jk>9) jk=getchar()-'0'; 13 while(jk>=0&&jk<=9) jg*=10,jg+=jk,jk=getchar()-'0'; 14 return jg; 15 } 16 struct tree 17 { 18 int lc,rc,sum; 19 }t[sj*50]; 20 void insert(int &x,int y,int l,int r,int v) 21 { 22 if(!x) x=++cnt; 23 t[x].lc=t[y].lc,t[x].rc=t[y].rc,t[x].sum=t[y].sum+1; 24 if(l==r) return; 25 int mid=l+r>>1; 26 if(v<=mid) t[x].lc=++cnt,insert(t[x].lc,t[y].lc,l,mid,v); 27 else t[x].rc=++cnt,insert(t[x].rc,t[y].rc,mid+1,r,v); 28 } 29 int query(int x,int la,int l,int r,int z,int y) 30 { 31 if(!x&&!la) return 0; 32 if(z<=l&&r<=y) return t[la].sum-t[x].sum; 33 int mid=l+r>>1; 34 if(y<=mid) return query(t[x].lc,t[la].lc,l,mid,z,y); 35 if(z>mid) return query(t[x].rc,t[la].rc,mid+1,r,z,y); 36 return query(t[x].lc,t[la].lc,l,mid,z,y)+query(t[x].rc,t[la].rc,mid+1,r,z,y); 37 } 38 int main() 39 { 40 n=read(); 41 for(int i=1;i<=n;i++) 42 { 43 a[i]=read(); 44 insert(rt[i],rt[i-1],1,n,a[i]); 45 tp+=query(rt[0],rt[i-1],1,n,a[i],n); 46 } 47 ans=tp; 48 for(int i=1;i<=n;i++) 49 for(int j=i+1;j<=n;j++) 50 { 51 if(a[i]<a[j]) continue; 52 nt=tp-2*query(rt[i],rt[j-1],1,n,a[j],a[i]); 53 if(nt<ans) ans=nt; 54 } 55 printf("%lld",ans); 56 return 0; 57 } 61pts 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<set> 5 #define ll long long 6 #define inf 0x7fffffff 7 using namespace std; 8 typedef pair<int,int> pa; 9 const int ss=300010; 10 int n,a[ss],ans,tp,q[ss],top,mx[ss],nt,d[ss]; 11 bool ad[ss],bd[ss]; 12 ll qwq; 13 set<pa> s; 14 set<pa>::iterator it,it2; 15 struct tree 16 { 17 int l,r,sum,lazy; 18 }t[ss<<2]; 19 inline int read() 20 { 21 int jg=0,jk=getchar()-'0'; 22 while(jk<0||jk>9) jk=getchar()-'0'; 23 while(jk>=0&&jk<=9) jg*=10,jg+=jk,jk=getchar()-'0'; 24 return jg; 25 } 26 void build(int x,int l,int r) 27 { 28 t[x].l=l,t[x].r=r,t[x].sum=-inf; 29 if(l==r) return; 30 int mid=l+r>>1; 31 build(x<<1,l,mid),build(x<<1|1,mid+1,r); 32 } 33 inline int maxx(int x,int y) 34 { 35 return x>y?x:y; 36 } 37 void pushdown(int x) 38 { 39 if(t[x].lazy) 40 { 41 t[x<<1].lazy+=t[x].lazy; 42 t[x<<1|1].lazy+=t[x].lazy; 43 t[x<<1].sum+=t[x].lazy; 44 t[x<<1|1].sum+=t[x].lazy; 45 t[x].lazy=0; 46 } 47 } 48 void modify(int x,int pos) 49 { 50 if(t[x].l==t[x].r) 51 { 52 t[x].sum=1; 53 return; 54 } 55 int mid=t[x].l+t[x].r>>1; 56 pushdown(x); 57 if(pos<=mid) modify(x<<1,pos); 58 else modify(x<<1|1,pos); 59 t[x].sum=maxx(t[x<<1].sum,t[x<<1|1].sum); 60 } 61 void update(int x,int z,int y,int v) 62 { 63 if(t[x].l==z&&t[x].r==y) 64 { 65 t[x].sum+=v; 66 t[x].lazy+=v; 67 return; 68 } 69 int mid=t[x].l+t[x].r>>1; 70 pushdown(x); 71 if(y<=mid) update(x<<1,z,y,v); 72 if(z>mid) update(x<<1|1,z,y,v); 73 if(z<=mid&&y>mid) 74 update(x<<1,z,mid,v),update(x<<1|1,mid+1,y,v); 75 t[x].sum=maxx(t[x<<1].sum,t[x<<1|1].sum); 76 } 77 int query(int x,int z,int y) 78 { 79 if(t[x].l==z&&t[x].r==y) return t[x].sum; 80 int mid=t[x].l+t[x].r>>1; 81 pushdown(x); 82 if(y<=mid) return query(x<<1,z,y); 83 if(z>mid) return query(x<<1|1,z,y); 84 return maxx(query(x<<1,z,mid),query(x<<1|1,mid+1,y)); 85 } 86 inline int lowbit(int x) 87 { 88 return x&(-x); 89 } 90 inline int getsum(int x) 91 { 92 int ret=0; 93 while(x) ret+=d[x],x-=lowbit(x); 94 return ret; 95 } 96 void update(int x,int v) 97 { 98 while(x<=n) d[x]+=v,x+=lowbit(x); 99 } 100 int main() 101 { 102 n=read(); 103 build(1,1,n); 104 for(int i=1;i<=n;i++) 105 { 106 a[i]=read(); 107 if(!top||a[i]>a[q[top]]) q[++top]=i,ad[i]=1; 108 qwq+=i-getsum(a[i])-1,update(a[i],1); 109 } 110 top=0; 111 for(int i=n;i>=1;i--) 112 if(!top||a[i]<a[q[top]]) 113 q[++top]=i,bd[i]=1; 114 for(int i=1;i<=n;i++) 115 { 116 if(bd[i]) 117 { 118 for(it=s.begin();it!=s.end()&&(*it).first<a[i];it=it2) 119 { 120 update(1,(*it).first,mx[(*it).second],-1); 121 it2=it,it2++; 122 s.erase(it); 123 } 124 tp=query(1,a[i],n)+1; 125 if(tp>ans) ans=tp; 126 } 127 if(ad[i]) modify(1,a[i]),nt=a[i]; 128 if(!ad[i]&&!bd[i]) 129 { 130 update(1,a[i],nt,1); 131 mx[i]=nt,s.insert(make_pair(a[i],i)); 132 } 133 } 134 if(ans>2) qwq-=(ans-2)*2; 135 printf("%lld",qwq); 136 return 0; 137 } 100pts

?

清華集訓2014 主旋律

? ? ? ? ?我會寫20分$n*2^n$暴力……這個總算是真DP題了，真·不會。miskcoo題解和popoqqq的代碼注釋。

?

轉(zhuǎn)載于:https://www.cnblogs.com/moyiii-/p/8798215.html

總結

以上是生活随笔為你收集整理的Team Task：DP的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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