首页 > 其他分享 >【做题笔记】Atcoder 之 dp 专题训练

【做题笔记】Atcoder 之 dp 专题训练

时间：2024-10-10 15:23:36浏览次数：7  
标签：Atcoder int sum cin 笔记 long dp define

A

B

C

D

E

F

G

H

I

概率 dp。

设 \(dp_{i,j}\) 表示前 \(i\) 个硬币中有 \(j\) 个正面的概率。转移显然：

\(dp_{i,j}=dp_{i-1,j-1}\times p_i+dp_{i-1,j}\times (1-p_i)\)

当 \(j=0\) 时，前 \(i\) 个硬币中没有正面。所以只能由反面的概率转移过来，转移为：

\(dp_{i,j}=dp_{i-1,j}\times (1-p_i)\)

初始化 \(dp_{0,0}=1\)。

时间复杂度 \(O(n^2)\)。

点击查看代码 
#include<bits/stdc++.h>
#define ll long long
#define For(i,l,r) for(int i=l;i<=r;++i)
#define FOR(i,r,l) for(int i=r;i>=l;--i)

using namespace std;

const int N = 3005;

double ans, p[N], dp[N][N];

int n;

signed main() {
  cin >> n;
  For(i,1,n) cin >> p[i];
  dp[0][0] = 1;
  For(i,1,n) {
    For(j,0,i) {
      if(j == 0) dp[i][j] = dp[i-1][j] * (1 - p[i]);
      else dp[i][j] = dp[i-1][j-1] * p[i] + dp[i-1][j] * (1 - p[i]);
    }
  }
  For(i,n/2+1,n) {
    ans += dp[n][i];
  }
  printf("%.10lf\n", ans);
  return 0;
}

J

K

博弈论 dp。

设 \(dp_i\) 表示剩下 \(i\) 个石子的胜败态。考虑到能走到必败态的就一定是必胜态，进行转移即可。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define For(i,l,r) for(int i=l;i<=r;++i)
#define FOR(i,r,l) for(int i=r;i>=l;--i)

using namespace std;

const int N = 105, M = 2e5 + 10;

int n, k, a[N];

bool dp[M];

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> k;
  For(i,1,n) cin >> a[i];
  For(j,0,k) {
    For(i,1,n) {
      if(a[i] <= j) dp[j] |= (dp[j-a[i]] == 0);
    }
  }
  cout << (dp[k] ? "First\n" : "Second\n");
  return 0;
}

L

M

数数 dp。

设 \(dp_{i,j}\) 表示前 \(i\) 个人分 \(j\) 块糖果的方案数。转移为：

\(dp_{i,j} = \sum\limits_{x=0}^{min(j,a_i)}dp_{i-1,j-x} = \sum\limits_{x=j-min(j,a_i)}^{j}dp_{i-1,x}\)

答案为 \(dp_{n,k}\)。

上者使用前缀和优化即可。

时间复杂度 \(O(nk)\)。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define For(i,l,r) for(int i=l;i<=r;++i)
#define FOR(i,r,l) for(int i=r;ri>=l;--i)
#define mod 1000000007

using namespace std;

const int N = 105, M = 1e5 + 10;

int n, K, a[N], dp[N][M], sum[N][M];

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> K;
  For(i,1,n) cin >> a[i];
  dp[0][0] = sum[0][0] = 1;
  For(i,1,K) sum[0][i] += sum[0][i-1]; 
  For(i,1,n) {
    For(j,0,K) {
      if(j == min(j,a[i])) dp[i][j] = sum[i-1][j] ;
      else dp[i][j] = (sum[i-1][j] - sum[i-1][j-min(j,a[i])-1] + mod) % mod;
      sum[i][j] = (sum[i][j-1] + dp[i][j]) % mod;
    }
  }
  cout << dp[n][K] << '\n';
  return 0;
}

N

O

状压 dp。

设 \(dp_{i,S}\) 表示左部点前 \(i\) 个点完全匹配，右部点状态为 \(S\) 的方案数。转移为：

\(dp_{i,S}=\sum\limits_{to(i,j)}dp_{i-1,S-j}\)，其中 \(S-j\) 表示 \(S\) 状态中去掉 \(j\) 的状态。同时要保证 \(S\) 状态中 \(j\) 的状态为 \(1\)。

答案为 \(dp_{n,2^n-1}\)

时间复杂度 \(O(n^2 2^n)\)，卡常可过。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define mod 1000000007

using namespace std;

const int N = 22, M = (1<<22)+1;

int n, a[N][N], dp[N][M], to[N][N], len[N];

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  For(i,1,n) {
    For(j,1,n) {
      cin >> a[i][j];
      if(a[i][j]) {
        to[i][++len[i]] = j;
      }
    }
  }
  dp[0][0] = 1;
  For(i,1,n) {
    For(j,1,len[i]) {
      int x = to[i][j]-1;
      for (int S = 0; S < (1<<n); S++) {
        if((S >> x) & 1) {
          dp[i][S] = (dp[i][S] + dp[i-1][S ^ (1 << x)]) % mod;
        }
      }
    }
  }
  cout << dp[n][(1<<n)-1] << '\n';
  return 0;
}

P

数数 dp，类似 没有上司的舞会

设 \(dp_{x,0/1}\) 表示 \(x\) 节点为白或黑点的方案数。转移为：

\(dp_{x,0}=\prod_{y\in son(x)} (dp_{y,0}+dp_{y,1})\)
\(dp_{x,1}=\prod_{y\in son(x)} dp_{y,0}\)

答案为 \(dp_{1,0}+dp_{1,1}\)。

时间复杂度 \(O(n)\)。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define For(i,l,r) for(int i=l;i<=r;++i)
#define FOR(i,r,l) for(int i=r;i>=l;--i)
#define mod 1000000007

using namespace std;

const int N = 1e5 + 10;

struct Node {
  int v, nx;
} e[N << 1];

int n, h[N], tot, dp[N][2];

void add(int u, int v) {
  e[++tot] = (Node){v, h[u]};
  h[u] = tot;
}

void dfs(int x, int fa) {
  dp[x][0] = dp[x][1] = 1;
  for (int i = h[x]; i; i = e[i].nx) {
    int y = e[i].v;
    if(y == fa) continue;
    dfs(y, x);
    dp[x][0] = (dp[x][0] * (dp[y][0] + dp[y][1]) % mod) % mod;
    dp[x][1] = (dp[x][1] * dp[y][0]) % mod;
  }
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  For(i,1,n-1) {
    int u, v;
    cin >> u >> v;
    add(u, v); add(v, u);
  } 
  dfs(1, 0);
  cout << (dp[1][0] + dp[1][1]) % mod;
  return 0;
}

Q

带权最长上升子序列

设 \(dp_i\) 表示以 \(i\) 结尾的最长上升子序列的最大权值。显然有：

\(dp_i=\max\limits_{j=1}^{i-1}dp_j+a_i\)

维护 \(dp\) 的前缀最大值并且支持插入数即可。树状数组即可胜任。

时间复杂度 \(O(n\log n)\)。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define For(i,l,r) for(int i=l;i<=r;++i)
#define FOR(i,r,l) for(int i=r;i>=l;--i)
#define mod 1000000007

using namespace std;

const int N = 2e5 + 10;

int n, h[N], a[N], t[N], dp[N], ans;

int lb(int x) {
  return x & -x;
}

void add(int x, int val) {
  for (int i = x; i <= N-2; i += lb(i)) {
    t[i] = max(t[i], val);
  }
}

int Max(int x) {
  int res = 0;
  for (int i = x; i; i -= lb(i)) {
    res = max(res, t[i]);
  }
  return res;
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  For(i,1,n) cin >> h[i];
  For(i,1,n) cin >> a[i];
  For(i,1,n) {
    dp[i] = Max(h[i]-1) + a[i];
    add(h[i], dp[i]);
    ans = max(ans, dp[i]);
  }
  cout << ans << '\n';
  return 0;
}

R

矩阵优化 dp。

设 \(dp_{k,i}\) 表示经过长度为 \(k\)，当前从某点转移至 \(i\) 的方案数。转移有：

\(dp_{k,i}=\sum\limits_{to(j,i)}dp_{k-1,j}\)

答案为 \(\sum\limits_{i=1}^n dp_{k,i}\)

可以发现每一次 sigma 内的转移都是固定的，这样重复有规律的转移可以用矩阵快速幂进行优化。

设计矩阵

\[\begin{bmatrix} a_{1,1}&a_{2,1}&\cdots&a_{n,1}\\ a_{1,2}&a_{2,2}&\cdots&a_{n,2}\\ \vdots&\vdots&\ddots&\vdots\\ a_{1,n}&a_{2,n}&\cdots&a_{n,n} \end{bmatrix} \]

对此矩阵进行 \(k\) 次快速幂，再与全 \(1\) 矩阵相乘。结果矩阵第一列即为答案。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define mod 1000000007

using namespace std;

const int N = 55;

int n, k, a[N][N], ans;

struct Matrix {
  int M[N][N];
  void clear() {
    For(i,1,n) For(j,1,n) M[i][j] = 0;
  }
  void init() {
    clear();
    For(i,1,n) M[i][i] = 1;
  }
  Matrix friend operator * (const Matrix &A, const Matrix &B) {
    Matrix Ans;
    Ans.clear();
    For(i,1,n) {
      For(j,1,n) {
        For(k,1,n) {
          Ans.M[i][j] = (Ans.M[i][j] + (A.M[i][k] * B.M[k][j]) % mod) % mod;
        }
      } 
    }
    return Ans;
  }
} dp;

Matrix qpow(Matrix a, int b) {
  Matrix res; res.init();
  for (; b; b >>= 1, a = a * a) {
    if(b & 1) res = res * a;
  }
  return res;
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> k;
  For(i,1,n) For(j,1,n) cin >> a[i][j];
  For(i,1,n) For(j,1,n) dp.M[i][j] = a[j][i];
  Matrix Res; Res.clear();
  For(i,1,n) Res.M[i][1] = 1;
  Res = qpow(dp, k) * Res;
  For(i,1,n) ans = (ans + Res.M[i][1]) % mod;
  cout << ans << '\n';
  return 0;
}

S

数位 dp。

设 \(dp_{pos,sum,0/1}\) 表示处理到第 \(pos\) 位，总和对 \(D\) 取模的结果为 \(sum\)，是否达到上限。

考虑记忆化搜索，每位数值从 \(0\) 枚举至 \(maxx\)。\(maxx\) 取值关乎于是否达到上限。

上限的判定为从高位至低位的前缀一致（\(K\) 的前缀）。当达到上限时，\(maxx\) 取 \(K\) 的第 \(pos\) 位即可。

答案满足要求显然就是 \(sum=0\) 时。

以上为搜索统计答案，只要记忆化一下即可。

时间复杂度 \(O(可过)\)。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define For(i,l,r) for(int i=l;i<=r;++i)
#define FOR(i,r,l) for(int i=r;i>=l;--i)
#define mod 1000000007

using namespace std;

const int N = 1e5 + 10, D = 105;

string k;

int n, d, num[N], dp[N][D][2];

int dfs(int pos, int res, int lim) {
  if(pos == 0) return (res == 0);
  if(dp[pos][res][lim] != -1) return dp[pos][res][lim];
  int ans = 0, maxx = (lim ? num[pos] : 9);
  For(i,0,maxx) {
    ans = (ans + dfs(pos - 1, (res + i) % d, lim && (i == maxx))) % mod;
  }
  return dp[pos][res][lim] = ans;
}

int ans() {
  memset(dp, -1, sizeof dp);
  For(i,1,n) num[i] = k[n-i+1] - '0';
  return dfs(n, 0, 1);
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> k >> d;
  n = k.size();
  k = " " + k;
  cout << (ans()-1+mod)%mod << '\n';
  return 0;
}

T

数数 dp。

设 \(dp_{i,j}\) 表示前 \(i\) 位填 \(1\) 至 \(i\)，当前位填 \(j\) 的方案数。

当 \(s_i='>'\)，当前位填的数要大于 \(i\)，所以 \(dp_{i,j}=\sum\limits_{k=j}^{i-1}dp_{i-1,k}\)

当 \(s_i='<'\)，当前位填的数要小于 \(i\)，所以 \(dp_{i,j}=\sum\limits_{k=1}^{j-1}dp_{i-1,k}\)

答案为 \(\sum\limits_{i=1}^n dp_{n,i}\)

使用前缀和优化即可。

时间复杂度 \(O(n^2)\)。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
#define mod 1000000007

using namespace std;

const int N = 3e3 + 10;

int n, dp[N][N], sum[N][N];

char s[N];

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  cin >> s + 2;
  dp[1][1] = sum[1][1] = 1;
  For(i,2,n) {
    For(j,1,i) {
      if(s[i] == '<') dp[i][j] = sum[i-1][j-1];
      else dp[i][j] = (sum[i-1][i-1] - sum[i-1][j-1] + mod) % mod;
      sum[i][j] = (sum[i][j-1] + dp[i][j]) % mod;
    } 
  }
  int ans = 0;
  For(i,1,n) ans = (ans + dp[n][i]) % mod;
  cout << ans << '\n';
  return 0;
}

U

看题解做出来的...

状压 dp。

设 \(dp_S\) 表示划分状态 \(S\) 的最大值。可以预处理出 \(val_S\) 表示状态 \(S\) 的贡献。

则转移为：

\(dp_S=\max\limits_{j\in{i的子集}} dp_{S \oplus j}+dp_{j}\)

答案为：\(dp_{2^n-1}\)

时间复杂度为 \(O(n^2 2^n+3^n)\)。可过。

点击查看代码 
#include<bits/stdc++.h>
#define int long long
#define For(i,l,r) for(int i=l;i<=r;++i)
#define FOR(i,r,l) for(int i=r;i>=l;--i)

using namespace std;

const int N = 17, M = (1<<17);

int n, a[N][N], val[M], dp[M];

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n;
  For(i,0,n-1) For(j,0,n-1) cin >> a[i][j];
  For(S,0,(1<<n)-1) {
    For(i,0,n-1) {
      For(j,0,i-1) {
        if(((S >> i) & 1) && ((S >> j) & 1)) val[S] += a[i][j];
      }
    }
  }
  For(S,0,(1<<n)-1) {
    dp[S] = val[S];
    for (int j = S; j; j = S & (j - 1)) {
      dp[S] = max(dp[S], dp[S^j] + dp[j]);
    }
  }
  cout << dp[(1<<n)-1] << '\n';
  return 0;
}

V

W

X

Y

Z

标签：Atcoder,int,sum,cin,笔记,long,dp,define
From： https://www.cnblogs.com/Daniel-yao/p/18449374

相关文章

  • 银行家算法小笔记
    最著名的避免死锁算法：将操作系统视为银行家，操作系统管理的资源视为银行家管理的资金。数据结构的描述假设n个进程，m类资源，银行家需要定义下面4个数据结构：可利用资源向量最大需求矩阵分配矩阵需求矩阵描述：设Requests_i是进程P-i的请求向量，Request_i[j]=K表示进程P-i需......
  • E62 树形DP P8677 [蓝桥杯 2018 国 A] 采油
    视频链接：  P8677[蓝桥杯2018国A]采油-洛谷|计算机科学教育新生态(luogu.com.cn)//树形DP+贪心O(nlogn)#include<bits/stdc++.h>#defineN100010usingnamespacestd;vector<int>e[N];intn,B[N],S[N],f[N],len;structman{intb,s;};boolcmp(manx,......
  • prometheus学习笔记之进程监控process_exporter
    项目地址：https://github.com/ncabatoff/process-exporter一、安装process-exporterhttps://github.com/ncabatoff/process-exporter/releases/download/v0.8.3/process-exporter-0.8.3.linux-amd64.tar.gztarxfprocess-exporter-0.8.3.linux-amd64.tar.gzmvprocess-expo......
  • 多线程面试笔记
    1-多线程与并发基础1.1-线程和进程的区别什么是线程和进程?进程：程序由指令和数据组成，但这些指令要运行，数据要读写，就必须将指令加载至CPU，数据加载至内存。在指令运行过程中还需要用到磁盘、网络等设备。进程就是用来加载指令、管理内存、管理IO的。当一个程序被运行，......
  • 《Programming from the Ground Up》阅读笔记：p217-p238
    《ProgrammingfromtheGroundUp》学习第11天，p217-p238总结，总计22页。一、技术总结1.Ccompilingp216,Ccompilingissplitintotwostages-thepreprocessorandthemaincompiler。注：感觉这个写法不好，因为preprocessor和compiler都是对象，这里应该指动作。应该是：Cco......
  • Bluespec SystemVerilog(BSV) 及 MIT 体系结构公开课 笔记
    前言早年MIT有三门用bsv作为硬件描述语言的体系结构课程，代号分别为6.004，6.175和6.375.根据MITCScourselist，现在这三门课分别改名为了6.1910、6.1920和6.5900.本文是自学这三门课所需的bsv时记录的笔记，内容主要来源于这三门课目前公开的资料（6.17516fall,6.375......
  • [编程笔记] 当前上下文中不存在名称"ViewBag"
    最近在弄另外一个项目，很长一段时间没接触MVC了，VisualStudio2022识别cshtml文件的时候，出了一点故障！很多ViewBag、@Html.Partial、@Html.FunctionBar()等这些地方都报波浪线了，提示不存在这个名称，但是代码是可以运行的，这种一般就是本地环境或者配置的问题了。......
  • 【Python脚本】getopt参数解析笔记
    getopt参数解析笔记背景在Python中，使用getopt模块进行命令行参数解析是常见的需求。在编写脚本时，正确地定义参数选项对于确保程序正常运行至关重要。这是一个用于检测安卓软件版本的脚本一部分，有些用法和笔记分享给大家问题描述在某个脚本中，使用getopt解析命令......
  • Android 笔记
    1，常用adb命令查看前台显示的Activity：adbshell"dumpsysactivity|grepmFocus" adbshelldumpsyswindow|findstrmCurrentFocus获取手机的分辨率：adbshellwmsize屏幕密度：adbshellwmdensity飞行模式开/关：adbshellsettingsputglobala......
  • 算法笔记（十五）——BFS 解决拓扑排序
    文章目录拓扑排序课程表课程表II火星词典拓扑排序有向无环图（DAG图）有向无环图指的是一个无回路的有向图AOV网：顶点活动图在有向无环图中，用顶点表示一个活动，用边来表示活动的先后顺序的图结构拓扑排序找到一个先后顺序，结果可能不唯一如何拓扑排序？找到一......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99