集訓(xùn)提高day2dp分治

動態(tài)規(guī)劃Scape動態(tài)規(guī)劃的本質(zhì)？都是狀態(tài)壓縮。本質(zhì)就是狀態(tài)壓縮只和答案有關(guān)的值。所以dp大概上就是一個不斷探索問題性質(zhì)減少那些和答案有關(guān)的值的個數(shù)。因為是要不斷探索問題性質(zhì)，所以要介紹DP還是從例題來介紹更好一點。類似背包的DP先來個簡單題m

100SRM625N個座位的圓桌,K個人去坐,任意時刻聯(lián)通塊數(shù)量

<=G?求方案數(shù)?NKG

2000BZOJ

2287N,m

2k退背包本質(zhì)上是多項式除一個單項式BZOJ

4033有一棵點數(shù)為N的樹，樹邊有邊權(quán)。給你一個在0~N之內(nèi)的正整數(shù)K，你要在這棵樹中選擇K個點，將其染成黑色，并將其他的N-K個點染成白色。將所有點染色后，你會獲得黑點兩兩之間的距離加上白點兩兩之間距離的和的收益。問收益最大值是多少。N<=2000BZOJ4753JSOI信息學(xué)代表隊一共有N名候選人，這些候選人從1到N編號。方便起見，JYY的編號是0號。每個候選人都由一位編號比他小的候選人Ri推薦。如果Ri=0則說明這個候選人是JYY自己看上的。為了保證團隊的和諧，JYY需要保證，如果招募了候選人i，那么候選人Ri”也一定需要在團隊中。當(dāng)然了，JYY自己總是在團隊里的。每一個候選人都有一個戰(zhàn)斗值Pi”，也有一個招募費用Si”。JYY希望招募K個候選人（JYY自己不算），組成一個性價比最高的團隊。也就是，這K個被JYY選擇的候選人的總戰(zhàn)斗值與總招募總費用的比值最大。N,k<=2500Bzoj

4987N,k

2k數(shù)位DPEg.

BZOJ1026windy定義了一種windy數(shù)。不含前導(dǎo)零且相鄰兩個數(shù)字之差至少為2的正整數(shù)被稱為windy數(shù)。windy想知道，

在A和B之間，包括A和B，總共有多少個windy數(shù)？AB

10^18BZOJ

1799給出a,b，求出[a,b]中各位數(shù)字之和能整除原數(shù)的數(shù)的個數(shù)SRM

522

Level

3G(x)表示x的fib進制下的數(shù)給定A

B求g(A)

xor

g(A+1)

xor

…

xor

g(B)A,B

10^15CF

908G令S(i)表示將i中所有數(shù)位上的數(shù)拿出來，從小到大排序后組成一個新的數(shù)的值。如S(50394)=3459。求\sum

S(i)。N<=10^700枚舉每個數(shù)字在排序后在第幾位，算貢獻F[i][j][k][p]表示前i個數(shù)，j個比他大的，k是是否已填進去，p表示是否卡著上界BZOJ

33291<=N<=10^18

狀壓DP旅行商問題N個點經(jīng)過每個點一次的最短路徑N<=20BZOJ2560銘銘有n個十分漂亮的珠子和若干根顏色不同的繩子?，F(xiàn)在銘銘想用繩子把所有的珠子連接成一個整體。

現(xiàn)在已知所有珠子互不相同，用整數(shù)1到n編號。對于第i個珠子和第j個珠子，可以選擇不用繩子連接，或者在ci,j根不同顏色的繩子中選擇一根將它們連接。如果把珠子看作點，把繩子看作邊，將所有珠子連成一個整體即為所有點構(gòu)成一個連通圖。特別地，珠子不能和自己連接。

銘銘希望知道總共有多少種不同的方案將所有珠子連成一個整體。由于答案可能很大，因此只需輸出答案對1000000007取模的結(jié)果。N<=15BZOJ4903BZOJ

3864給一個長度<=15的串S（僅包含ACGT），對于所有的i（0<=i<=|S|），求有多少長度為M的串T滿足串T和串S的最長公共子序列長度為i。

BZOJ

4197為了慶祝NOI的成功開幕，主辦方為大家準備了一場壽司晚宴。小G和小W作為參加NOI的選手，也被邀請參加了壽司晚宴。在晚宴上,主辦方為大家提供了n?1種不同的壽司，編號1,2,3,…,n?1，其中第i種壽司的美味度為i+1（即壽司的美味度為從2到n）?，F(xiàn)在小G和小W希望每人選一些壽司種類來品嘗，他們規(guī)定一種品嘗方案為不和諧的當(dāng)且僅當(dāng)：小G品嘗的壽司種類中存在一種美味度為x的壽司，小W品嘗的壽司中存在一種美味度為y的壽司，而x與y不互質(zhì)?，F(xiàn)在小G和小W希望統(tǒng)計一共有多少種和諧的品嘗壽司的方案（對給定的正整數(shù)p取模）。注意一個人可以不吃任何壽司。N<=500BZOJ

4006小銘銘最近進入了某情報部門，該部門正在被如何建立安全的通道連接困擾。該部門有n個情報站，用1到n的整數(shù)編號。給出m對情報站ui;vi和費用wi，表示情報站ui和vi之間可以花費wi單位資源建立通道。如果一個情報站經(jīng)過若干個建立好的通道可以到達另外一個情報站，那么這兩個情報站就建立了通道連接。形式化地，若ui和vi建立了通道，那么它們建立了通道連接；若ui和vi均與ti建立了通道連接，那么ui和vi也建立了通道連接?，F(xiàn)在在所有的情報站中，有p個重要情報站，其中每個情報站有一個特定的頻道。小銘銘面臨的問題是，需要花費最少的資源，使得任意相同頻道的情報站之間都建立通道連接。N<=1000,m<=3000,p<=10帶容斥DPTopCoderSRM684600ptsDivFree一個長度為n的序列，滿足每個元素都是[1,k]內(nèi)的整數(shù)，且對于相鄰的兩個元素a=Si,b=Si+1，有a<=b或amodb≠0。求這樣的序列的個數(shù)模1000000007。n,k<=50000.agc005DMythologicalsama喜歡排列。因為她不喜歡整數(shù)K，她的排列會滿足以下條件。對于一個排列$a_1,a_2,\cdots,a_N$,對于任意的$1\leqi\leqn$,$|a_i-i|\not=K$請問有多少長度為$N$的排列滿足以上條件？請輸出答案對$924844033$(一個質(zhì)數(shù))取模的答案$n\leq2000$SHOI2009舞會N個男生N個女生，各自都有身高。我們要將他們配成N對，使得不超過K對男的比女的高。N<=200需要高精度首先我們枚舉一個男生的集合，這些男生都高于他的舞伴。具體的做法可以使用dp,從低到高考慮每個人，dp[i][j]表示前i個男生選了j個方案。對于剩下的人可以隨便亂連，也就是dp[n][j]*(n-j)!也就是求出了有k個人，使得男生比女生高的方案f(k)。然后算出恰好k個男生比女生高的方案。