五一普轉(zhuǎn)提筆記Day-4
樹形dp(自下而上)↓
T1
分析維度:f[i]表示以i為根的子樹的所有點到i的距離之和。
初始化:f[1]=0
轉(zhuǎn)移:
但是如果我們枚舉每一個i，那就TLE了，此時我們就要使用換根dp，用原來一個點的結(jié)果在O(n)的時間內(nèi)算出其他點的結(jié)果(自上而下)，如下圖:
完整代碼:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1e5+1;
vector<int> z[maxn];
int f[maxn],ans,n;
int size[maxn];
void dfs(int now,int fa){
for(auto x : z[now]){
if(x!=fa){
dfs(x,now);
}
}
f[now]=0;
size[now]=1;
for(auto x : z[now]){
if(x!=fa){
size[now]+=size[x];
f[now]+=f[x]+size[x];
}
}
}
void dfs(int now,int fa,int sum){
ans=min(ans,f[now]+sum);
for(auto x: z[now]){
if(x!=fa){
dfs(x,now,sum+f[now]-(f[x]+size[x])+(n-size[x]));
}
}
}
signed main(){
cin>>n;
for(int i=1;i<n;i++){ // 樹有n-1條邊
int u,v;
cin>>u>>v;
z[u].push_back(v);
z[v].push_back(u);
}
dfs(1,0);
return 0;
}
T2求樹上一點到其他點的距離和的和
分析維度:f[i]表示i的子樹內(nèi)所有經(jīng)過i的路徑的權(quán)值之和。
g[i]:i的子樹內(nèi)以i為起點的路徑之和。
求值:
但是這里復(fù)雜度太高了，我們可以用一種更簡單的方法去做(牛客輸入不了公式，我只能截圖了):
T3給定一棵樹（連通無環(huán)圖），其中某些節(jié)點被標(biāo)記。定義：f[i]：節(jié)點?i?到所有被標(biāo)記節(jié)點的最遠(yuǎn)距離。目標(biāo)：找到所有?f[i]??的最小值，要求時間復(fù)雜度O(n)
分析維度:g[i]i的子樹內(nèi)被標(biāo)記的節(jié)點到i的距離的最大值
方法:附上一張圖:
狀壓dp↓
狀壓:狀態(tài)壓縮(把一個數(shù)組轉(zhuǎn)化為一個數(shù),從而存在狀態(tài)里面)。
T1一個平面上有n個點，坐標(biāo)為(x,y)，從一號點出發(fā)把所有點走一遍，是距離之和最小。
分析維度:變化的量有:走到哪里了、哪些點已經(jīng)走過了、當(dāng)前距離。所以f[j][i]表示走到i點已經(jīng)走過點j時當(dāng)前的距離，但此時j是一個數(shù)組，就需要用二進(jìn)制狀態(tài)壓縮把每一個點是否走過記錄下來，走過記1，否則記0，如:100010。復(fù)雜度(n^2*2n)，n的范圍需要小于18。
代碼：
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int maxn=1001;
double f[1<<maxn][maxn];
int n,x[maxn],y[maxn];
double dis(int j,int k){
double dx=x[j]-x[k];
double dy=y[j]-y[k];
return sqrt(dx*dx+dy*dy);
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
for(int i=0;i<(1<<n);i++){
for(int j=0;j<n;j++){
f[i][j]=1e20;
}
}
f[1][0]=0;
for(int i=0;i<(1<<n);i++){
for(int j=0;j<n;j++){
if(i>>j&1)//i的二進(jìn)制第j位是1才是合法的狀態(tài)
{
for(int k=0;k<n;k++){
if((i>>k&1)==0){
f[i|(1<<k)][k]=min(f[i|(1<<k)][k],f[i][j]+dis(j,k));
}
}
}
}
}
double ans = 1e20;
for(int j = 1; j < n; j++) {
ans = min(ans, f[(1<<n)-1][j] + dis(j, 0));
}
printf("%.2lld",ans);
return 0;
}
T2在N×N?的棋盤上放置?K?個國王，要求它們互不攻擊（即任意兩個國王不能相鄰，包括上下左右和對角線方向）。求合法的擺放方案數(shù)。
分析維度:變量:放了幾個國王和方案數(shù)。方法有兩種:F1一個一個格子放；F2一行一行放。先說F2現(xiàn)在多一個變量:放在第幾行了，也要知道上一行哪里有國王，也要記錄上一行哪里有國王。f[i][j][s]代表1~i行已經(jīng)放完，總共放了j個國王，s代表第i行哪些位置有國王(使用狀態(tài)壓縮)。枚舉第i+1行如何放國王。復(fù)雜度O(nk2^(2n)),代碼如下:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=1e2;
int n,k;
int f[maxn][maxn][maxn];
signed main(){
cin>>n>>k;
f[0][0][0]=1;
for(int i=0;i<n;i++){
for(int j=0;j<=k;j++){
for(int s=0;s<(1<<n);s++){
if(f[i][j][s]){
for(int r=0;r<(1<<n);r++){
if(r&s) continue;
if((r>>1)&s) continue;
if((r<<1)&s) continue;
if((r<<1)&r) continue;
f[i+1][j+__builtin_popcount(r)][r]+=f[i][j][s];
}
}
}
}
}
long long ans=0;
for(int s=0;s<(1<<n);s++){
ans += f[n][k][s];
}
cout<<ans<<endl;
return 0;
}
再說F1，我們也要有順序，從第一行開始往下放。但這樣做有一個好處，再放這一個格子時，只用考慮放或不放。f[i][j][k][s]表示放到(i,j)，放了k個國王，輪廓線上放或未放國王，f[i][j][k][s]=方案數(shù)，應(yīng)狀壓s。代碼如下:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn=10;
int f[maxn][maxn][maxn][maxn],n,k;//f[i][j][k][s]
int main()
{
cin >> n >> k;
f[1][0][0][0] = 1;
//O(n^2k2^(n+1))
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)//要在第i行第j列這個格子放國王
{
for (int r=0;r<=k;r++)
for (int s=0;s<(1<<(n+1));s++)
if (f[i][j-1][r][s])//方案數(shù)不為0
{
//ij不放國王
f[i][j][r][(s|(1<<(j-1)))^(1<<(j-1))] += f[i][j-1][r][s];
//ij放國王
if (j>=2 && (s>>(j-2)&1)==1) continue;
if (j>=1 && (s>>(j-1)&1)==1) continue;
if ((s>>j&1)==1) continue;
if ((s>>(j+1)&1)==1) continue;
f[i][j][r+1][s|(1<<(j-1))] += f[i][j-1][r][s];
}
for (int r=0;r<=k;r++)
for (int s=0;s<(1<<(n+1));s++)
f[i+1][0][r][(s & ((1<<n)-1) << 1)] = f[i][j][r][s];
}
long long ans=0;
for(int s=0;s<(1<<n);s++){
ans += f[n][0][k][s]; // 第n行第0列，放了k個國王
}
cout<<ans<<endl;
}
總結(jié):狀壓DP中，哪個的數(shù)據(jù)范圍小就狀壓哪一個。
T3農(nóng)場主 John 有一塊?M×NM=的牧場（1≤M,N≤12），某些格子貧瘠不能種草。要求在能種草的格子上選擇若干塊草地，滿足：1.沒有兩塊草地相鄰（上下左右方向）。2.不考慮草地總數(shù)（包括一塊不選的方案）。求所有合法的種植方案
這道題只是提了一嘴，沒講。
DP優(yōu)化↓
使用數(shù)據(jù)結(jié)構(gòu)優(yōu)化
T1給定一個長度為?N的序列，每個位置有一個目標(biāo)顏色。初始時，所有位置都沒有顏色。每次操作可以選擇一個區(qū)間，將該區(qū)間內(nèi)的所有元素設(shè)置為它們的目標(biāo)顏色。設(shè)該區(qū)間內(nèi)不同顏色的數(shù)量為?X，則操作的代價為?X^2。求將所有位置染成目標(biāo)顏色的最小總代價。N≤5*10^4。(來源于HDU(5009))
分析:染色順序?qū)Υ鸢笡]有影響，就定義順序為自前向后，可以分為若干塊先算。定義f[i]為把1~i完成的最小代價，此時轉(zhuǎn)移方程為f[i]=(f[j]+(j-i+1)^2)min，時間復(fù)雜度為O(n^2)，肯定超時，我們就要使用數(shù)據(jù)結(jié)構(gòu)優(yōu)化。我們通過觀察不難發(fā)現(xiàn)，最優(yōu)解一定≤n^2，但是不管它怎么給數(shù)據(jù)，一定有一種方案是每次只染一塊，這樣代價就為1，所以其實最優(yōu)解≤n。所以每一塊的x≤√n，維護(hù)從i開始向前走，保證前面有j種顏色最遠(yuǎn)走到哪里(1≤j≤√n)只要可以維護(hù)好這√n種方案，時間復(fù)雜度可降至O(n√n)，可以使用雙指針實現(xiàn)，這樣就不會超時了。
T2①一塊地只能被種一次；②一塊地可以被種多次Hja 回到老家開始種地，由于太久沒有種地，所以所有地都是荒地。將每片地從荒地變成不荒地有一定的代價，但是一旦改變之后就不再是荒地了。現(xiàn)在 Hja 要開始 M 年的種地生活，第 i 年 Hja 可以在 ( l_i ) 到 ( r_i ) 塊地上種地，并且可以獲得 ( p_i ) 的收益。（注意，要種地必須整段一起種，并且這些地一定已經(jīng)是不荒地），Hja 可以選擇種或者不種每一年的地，問 Hja 能夠獲得的最大收益。其中，N、M≤1000。
分析:我們可以設(shè)f[i][s]表示在第i年有s塊地不是荒地，從而去用DP暴力計算，但是時間復(fù)雜度太高了。我們可以提前把所有要用的地開荒，后面種地的順序就沒有影響，我們可以把這M年的順序按照某種方式排序。我們就不需要記錄哪些地開荒了，哪些地沒開荒，接下來就要思考按照哪種方法排序。以左端點為第一關(guān)鍵字，右端點為第二關(guān)鍵字進(jìn)行排序，此時是最優(yōu)的。此時我們讓f[i][s]代表前i年的種地已經(jīng)結(jié)束了，即前i次種地已經(jīng)完成，在所有開荒的地中，最右邊的是j，此時的最小代價。我們有需要分情況討論了。
①j<l_i+1
②l_i+1≤j≤r_i+1
③r_i+1≤r
完整代碼:
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1005;
int n, m;
int a[N], sum[N], l[N], r[N], p[N], f[N][N];
int main() {
cin >> n >> m;
for(int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i-1] + a[i]; // 計算前綴和
}
for(int i = 1; i <= m; i++) {
cin >> l[i] >> r[i] >> p[i];
}
memset(f, -0x3f, sizeof f); // 初始化為負(fù)無窮
f[0][0] = 0; // 初始狀態(tài)
for(int i = 0; i < m; i++) {
for(int j = 0; j <= n; j++) {
// 不種第i+1年
f[i+1][j] = max(f[i+1][j], f[i][j]);
// 種第i+1年
if(j < l[i+1]) {
f[i+1][r[i+1]] = max(f[i+1][r[i+1]], f[i][j] + p[i+1] - (sum[r[i+1]] - sum[l[i+1]-1]));
}
else if(j <= r[i+1]) {
f[i+1][r[i+1]] = max(f[i+1][r[i+1]], f[i][j] + p[i+1] - (sum[r[i+1]] - sum[j]));
}
else {
f[i+1][j] = max(f[i+1][j], f[i][j] + p[i+1]);
}
}
}
int ans = 0;
for(int j = 0; j <= n; j++) {
ans = max(ans, f[m][j]);
}
cout << ans << endl;
return 0;
}
但如果M、N≤2*10^5,那就超時了，因為時間復(fù)雜度O(mn)。此時我們可以用滾動，
①j<l_i+1
②l_i+1≤j≤r_i+1
③r_i+1≤r
T3CF193D
我們看到這道題后先想到暴力，但時間復(fù)雜度為O(n^5),直接超時了。我們就可以使用數(shù)據(jù)結(jié)構(gòu)優(yōu)化。(思路圖沒截到 qwq)
數(shù)位dp
核心:在l~r滿足條件的數(shù)有多少個或還是多少
T1 f(123)=1+2+3=6 求f(l)+…………+f(r)的值。(1≤l,r≤n)
我們要從第n位開始填充數(shù)字。
代碼:
#include <bits/stdc++.h>
using namespace std;
int a[20];
long long f[20][2], g[20][2];
long long dp(long long x) {
int len = 0;
while (x > 0) {
a[++len] = x % 10;
x /= 10;
}
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
f[len + 1][1] = 0;
g[len + 1][1] = 1;
for (int i = len; i >= 1; i--) {
for (int tight = 0; tight < 2; tight++) {
if (g[i + 1][tight]) {
int upper = (tight == 1) ? a[i] : 9;
for (int d = 0; d <= upper; d++) {
int newTight = (tight == 1) && (d == upper);
f[i][newTight] += f[i + 1][tight] + g[i + 1][tight] * d;
g[i][newTight] += g[i + 1][tight];
}
}
}
}
return f[1][0] + f[1][1];
}
int main() {
long long l, r;
cin >> l >> r;
cout << dp(r) - dp(l - 1) << endl;
return 0;
}
T2P2657
訣竅:多一個變量就多一個維度。
與上一題相似，就不寫分析了，直接上代碼。
#include <bits/stdc++.h>
using namespace std;
int a[20];
long long f[20][2][10]; // f[pos][tight][last]
long long dp(long long x) {
int n = 0;
while (x > 0) {
a[++n] = x % 10;
x /= 10;
}
memset(f, 0, sizeof(f));
f[n + 1][1][0] = 1;
for (int i = n; i >= 1; i--) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 10; k++) {
if (f[i + 1][j][k]) {
int up= 9;
if(j==1) up=a[i];
for (int d = 0; d <= up; d++) {
if (k == 0) {
if (d == 0) continue;
int newTight = (j == 1) && (d == up);
f[i][newTight][d] += f[i + 1][j][k];
} else {
if (abs(d - k) < 2) continue;
int newTight = (j == 1) && (d == up);
f[i][newTight][d] += f[i + 1][j][k];
}
}
}
}
}
}
long long ans = 0;
for (int tight = 0; tight < 2; tight++) {
for (int last = 0; last < 10; last++) {
ans += f[1][tight][last];
}
}
return ans;
}
int main() {
long long l, r;
cin >> l >> r;
cout << dp(r) - dp(l - 1) << endl;
return 0;
}
后語↓
回家要把題做完，并不要求急性地做，可以慢慢做。暑假是最好的時間，ppt上有題可以交到這個網(wǎng)站 。要想要拿到高分，要盡量多拿分，不丟分，做題時盡量一次過，多給自己點時間檢查。