五一普转提笔记Day-4
树形dp(自下而上)↓
T1
分析维度:f[i]表示以i为根的子树的所有点到i的距离之和。
初始化:f[1]=0
转移:
但是如果我们枚举每一个i，那就TLE了，此时我们就要使用换根dp，用原来一个点的结果在O(n)的时间内算出其他点的结果(自上而下)，如下图:
完整代码:
#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的子树内所有经过i的路径的权值之和。
g[i]:i的子树内以i为起点的路径之和。
求值:
但是这里复杂度太高了，我们可以用一种更简单的方法去做(牛客输入不了公式，我只能截图了):
T3给定一棵树（连通无环图），其中某些节点被标记。定义：f[i]：节点 i 到所有被标记节点的最远距离。目标：找到所有 f[i] 的最小值，要求时间复杂度O(n)
分析维度:g[i]i的子树内被标记的节点到i的距离的最大值
方法:附上一张图:
状压dp↓
状压:状态压缩(把一个数组转化为一个数,从而存在状态里面)。
T1一个平面上有n个点，坐标为(x,y)，从一号点出发把所有点走一遍，是距离之和最小。
分析维度:变化的量有:走到哪里了、哪些点已经走过了、当前距离。所以f[j][i]表示走到i点已经走过点j时当前的距离，但此时j是一个数组，就需要用二进制状态压缩把每一个点是否走过记录下来，走过记1，否则记0，如:100010。复杂度(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位是1才是合法的状态
{
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 个国王，要求它们互不攻击（即任意两个国王不能相邻，包括上下左右和对角线方向）。求合法的摆放方案数。
分析维度:变量:放了几个国王和方案数。方法有两种:F1一个一个格子放；F2一行一行放。先说F2现在多一个变量:放在第几行了，也要知道上一行哪里有国王，也要记录上一行哪里有国王。f[i][j][s]代表1~i行已经放完，总共放了j个国王，s代表第i行哪些位置有国王(使用状态压缩)。枚举第i+1行如何放国王。复杂度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]=方案数，应状压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])//方案数不为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;
}
总结:状压DP中，哪个的数据范围小就状压哪一个。
T3农场主 John 有一块 M×NM=的牧场（1≤M,N≤12），某些格子贫瘠不能种草。要求在能种草的格子上选择若干块草地，满足：1.没有两块草地相邻（上下左右方向）。2.不考虑草地总数（包括一块不选的方案）。求所有合法的种植方案
这道题只是提了一嘴，没讲。
DP优化↓
使用数据结构优化
T1给定一个长度为 N的序列，每个位置有一个目标颜色。初始时，所有位置都没有颜色。每次操作可以选择一个区间，将该区间内的所有元素设置为它们的目标颜色。设该区间内不同颜色的数量为 X，则操作的代价为 X^2。求将所有位置染成目标颜色的最小总代价。N≤5*10^4。(来源于HDU(5009))
分析:染色顺序对答案没有影响，就定义顺序为自前向后，可以分为若干块先算。定义f[i]为把1~i完成的最小代价，此时转移方程为f[i]=(f[j]+(j-i+1)^2)min，时间复杂度为O(n^2)，肯定超时，我们就要使用数据结构优化。我们通过观察不难发现，最优解一定≤n^2，但是不管它怎么给数据，一定有一种方案是每次只染一块，这样代价就为1，所以其实最优解≤n。所以每一块的x≤√n，维护从i开始向前走，保证前面有j种颜色最远走到哪里(1≤j≤√n)只要可以维护好这√n种方案，时间复杂度可降至O(n√n)，可以使用双指针实现，这样就不会超时了。
T2①一块地只能被种一次；②一块地可以被种多次Hja 回到老家开始种地，由于太久没有种地，所以所有地都是荒地。将每片地从荒地变成不荒地有一定的代价，但是一旦改变之后就不再是荒地了。现在 Hja 要开始 M 年的种地生活，第 i 年 Hja 可以在 ( l_i ) 到 ( r_i ) 块地上种地，并且可以获得 ( p_i ) 的收益。（注意，要种地必须整段一起种，并且这些地一定已经是不荒地），Hja 可以选择种或者不种每一年的地，问 Hja 能够获得的最大收益。其中，N、M≤1000。
分析:我们可以设f[i][s]表示在第i年有s块地不是荒地，从而去用DP暴力计算，但是时间复杂度太高了。我们可以提前把所有要用的地开荒，后面种地的顺序就没有影响，我们可以把这M年的顺序按照某种方式排序。我们就不需要记录哪些地开荒了，哪些地没开荒，接下来就要思考按照哪种方法排序。以左端点为第一关键字，右端点为第二关键字进行排序，此时是最优的。此时我们让f[i][s]代表前i年的种地已经结束了，即前i次种地已经完成，在所有开荒的地中，最右边的是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[0][0] = 0; // 初始状态
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,那就超时了，因为时间复杂度O(mn)。此时我们可以用滚动，
①j<l_i+1
②l_i+1≤j≤r_i+1
③r_i+1≤r
T3CF193D
我们看到这道题后先想到暴力，但时间复杂度为O(n^5),直接超时了。我们就可以使用数据结构优化。(思路图没截到 qwq)
数位dp
核心:在l~r满足条件的数有多少个或还是多少
T1 f(123)=1+2+3=6 求f(l)+…………+f(r)的值。(1≤l,r≤n)
我们要从第n位开始填充数字。
代码:
#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上有题可以交到这个网站 。要想要拿到高分，要尽量多拿分，不丢分，做题时尽量一次过，多给自己点时间检查。
查看7道真题和解析