目录
DP实录
还有一些水题，就不写进来了，感觉1600,1700的dp好水啊。。
CF 1447E div2
建出trie树来，然后答案是保证每个点最多有一个子树有多个叶子的情况下最少删除叶子的个数。
//https://www.cnblogs.com/Cwolf9/p/10599500.html
#include <bits/stdc++.h>
#define fi first
#define se second
#define o2(x) (x) * (x)
#define mk make_pair
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset((a), (b), sizeof((a)))
#define rep(i, s, t) for(register int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(register int i = (s), LIM=(t); i >= LIM; --i)
#define GKD std::ios::sync_with_stdio(false);cin.tie(0)
#define my_unique(x) sort(all(x)), x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef long long int64;
typedef unsigned long long uint64;
typedef pair<int, int> pii;
// mt19937 rng(time(NULL));//std::clock()
// mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
// shuffle(arr, arr + n, rng64);
inline int64 read() {
int64 x = 0;int f = 0;char ch = getchar();
while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch =
getchar(); return x = f ? -x : x;
}
inline void write(int64 x, bool f = true) {
if (x == 0) {putchar('0'); if(f)putchar('
');else putchar(' ');return;}
if (x < 0) {putchar('-');x = -x;}
static char s[23];
int l = 0;
while (x != 0)s[l++] = x % 10 + 48, x /= 10;
while (l)putchar(s[--l]);
if(f)putchar('
');else putchar(' ');
}
int lowbit(int x) { return x & (-x); }
template <class T>
T big(const T &a1, const T &a2) {return a1 > a2 ? a1 : a2;}
template <class T>
T sml(const T &a1, const T &a2) {return a1 < a2 ? a1 : a2;}
template <typename T, typename... R>
T big(const T &f, const R &... r) {return big(f, big(r...));}
template <typename T, typename... R>
T sml(const T &f, const R &... r) {return sml(f, sml(r...));}
void debug_out() { cout << '
'; }
template <typename T, typename... R>
void debug_out(const T &f, const R &... r) {
cout << f << " ";
debug_out(r...);
}
#ifdef LH_LOCAL
#define debug(...) cout << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__);
#else
#define debug(...) ;
#endif
/*================Header Template==============*/
const int INF = 0x3f3f3f3f;
const int mod = 998244353;// 998244353
const int MXN = 2e5 + 5;
const int MXE = MXN * 30;
const int base = 29;//TODO
int n, m;
int ar[MXN], fa[MXN], siz[MXN];
int nex[MXE][2], cnt[MXE], who[MXE], inde;
int dp[MXE];
int Fi(int x) {
int rt = x;
while(fa[rt] != rt) {
rt = fa[rt];
}
while(fa[x] != rt) {
int px = fa[x];
fa[x] = rt;
x = px;
}
return rt;
}
void ins(int x, int w) {
int rt = 0;
per(i, base, 0) {
int now = (x >> i) & 1;
if(nex[rt][now] == -1) {
nex[rt][now] = ++ inde;
clr(nex[inde], -1);
}
rt = nex[rt][now];
++ cnt[rt];
}
who[rt] = w;
debug(rt, ar[w])
}
void del(int x) {
int rt = 0;
per(i, base, 0) {
int now = (x >> i) & 1;
rt = nex[rt][now];
-- cnt[rt];
}
}
int findv(int x) {
int rt = 0;
per(i, base, 0) {
int now = (x >> i) & 1;
if(nex[rt][now] != -1 && cnt[nex[rt][now]]) rt = nex[rt][now];
else rt = nex[rt][!now];
}
return who[rt];
}
/**
* dp[i] = 保证每个点最多有一个子树有多个叶子的情况下最少删除叶子的个数
*/
void dfs(int u, int ba) {
debug(u, ba)
int sum = 0;
vector<int> vs;
rep(i, 0, 2) {
if(nex[u][i] != -1) {
dfs(nex[u][i], u);
if(cnt[nex[u][i]] > 1) sum += cnt[nex[u][i]] - 1, vs.eb(nex[u][i]);
}
}
if(vs.size() == 1) dp[u] = dp[vs[0]];
else if((int)vs.size() > 1) {
dp[u] = INF;
for(int x: vs) dp[u] = min(dp[u], dp[x] + sum - cnt[x] + 1);
}
//debug(u, dp[u])
vector<int>().swap(vs);
}
void work() {
clr(nex[0], -1);
n = read();
rep(i, 1, n + 1) {
fa[i] = i;
ar[i] = read();
ins(ar[i], i);
}
dfs(0, -1);
rep(i, 1, n + 1) {
del(ar[i]);
int x = findv(ar[i]);
ins(ar[i], i);
int px = Fi(i), py = Fi(x);
//debug(i, x, px, py)
if(px == py) continue;
fa[py] = px;
}
printf("%d
", dp[0]);
}
int main() {
#ifdef LH_LOCAL
//freopen("D:\ACM\mtxt\in.txt", "r", stdin);
#endif
for(int cas = 1, tim = 1; cas <= tim; ++ cas) {
// printf("Case #%d:
", cas);
work();
}
#ifdef LH_LOCAL
cout << "time cost:" << 1.0 * clock() / CLOCKS_PER_SEC << "s" << endl;
// system("pause");
#endif
return 0;
}
CF 999F div3 2200
果然div3大部分都是水题。。。
(n:500,k:10)
(n)个人，每人分(k)张卡片，问所有人愉悦值总和
每个人有自己喜欢的卡片编号，分到(i)张喜欢卡片的愉悦值为(h_i)
把有同种喜好的人放在一起(dp)，最多$dp(500次
)dp[i][j](表示把)i(个卡片分成)j(堆的最多价值和
状态转移：枚举第)j$堆里面放多少张他喜欢卡片
#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long LL;
const int MXN = 1e5 + 7;
const int mod = 998244353;
int n, k;
int cr[MXN], fr[MXN], hr[MXN];
int gao(int val, int cnt) {
int all = 0, a = lower_bound(cr+1, cr+1+n*k, val) - cr;
if(a < 1 + n*k && cr[a] == val) {
int b = upper_bound(cr+1, cr+1+n*k, val) - cr;
all = b - a;
}
cnt = min(all, cnt);
vector <vector <int>> dp(all+1,vector <int> (cnt+1, 0));
for(int i = 1; i <= all; ++i) {
for(int j = 1; j <= cnt; ++j) {
for(int K = 1; K <= min(k, i); ++K) {
dp[i][j] = max(dp[i-K][j-1] + hr[K], dp[i][j]);
}
}
}
return dp[all][cnt];
}
int main() {
#ifndef ONLINE_JUDGE
freopen("./文档/acm/in.txt", "r", stdin);
printf("*Cwolf9*
");
//freopen("out.txt", "w", stdout);
#endif
scanf("%d%d", &n, &k);
for(int i = 1; i <= n*k; ++i) scanf("%d", &cr[i]);
for(int i = 1; i <= n; ++i) scanf("%d", &fr[i]);
for(int i = 1; i <= k; ++i) scanf("%d", &hr[i]);
sort(cr + 1, cr + 1 + n * k);
sort(fr + 1, fr + 1 + n);
LL ans = 0;
int cnt = 1;
for(int i = 2; i <= n; ++i) {
if(fr[i] == fr[i-1]) {
++ cnt;
if(i == n) ans += gao(fr[i], cnt);
}else {
ans += gao(fr[i-1], cnt);
cnt = 1;
if(i == n) ans += gao(fr[i], 1);
}
}
if(n == 1) ans += gao(fr[1], 1);
printf("%lld
", ans);
return 0;
}
LightOJ - 1236
200组求下面这个石子
long long pairsFormLCM( LL n ) {
long long res = 0;
for( int i = 1; i <= n; i++ )
for( int j = i; j <= n; j++ )
if( lcm(i, j) == n ) res++; // lcm means least common multiple
return res;
}
注意是无序对。
(n)唯一素因子分解为：(p_1^{c_1}*...*p_k^{c_k})
若(lcm(A,B) = n)，(A=p_1^{a_1}*...*p_k^{a_k})，(B=p_1^{b_1}*...*p_k^{b_k})，则肯定有：
(max(a_i,b_i)=c_i,;;1le ile k)
所以很明显答案是：(sum_{i=1}^k f(i))
(f(i))表示(max(a_i,b_i)=c_i)的方案数，明显(f(i)=2*(c_i+1)-1)
因为(n)最大为(1e14)，最大的平方素因子也不会超过(1e7)，所以本题线性筛到(1e7)就可以对它素因子分解啦。
复杂度：(200*log(n))
#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long LL;
const int MXN = 1e7 + 7;
const int mod = 998244353;
LL n;
int pp[MXN/11], pcnt;
bool noprime[MXN];
void init() {
noprime[0] = noprime[1] = 1;
for(int i = 2; i < MXN; ++i) {
if(!noprime[i]) pp[pcnt++] = i;
for(int j = 0; j < pcnt && pp[j] * i < MXN; ++j) {
noprime[pp[j] * i] = 1;
if(i % pp[j] == 0) break;
}
}
}
int main() {
#ifndef ONLINE_JUDGE
//freopen("./文档/acm/in.txt", "r", stdin);
//printf("*Cwolf9*
");
//freopen("out.txt", "w", stdout);
#endif
init();
int tim, cas = 0; scanf("%d", &tim);
while(tim --) {
scanf("%lld", &n);
LL t = n, ans = 1;
for(int i = 0; i < pcnt && (LL)pp[i] * pp[i] <= n; ++i) {
int cnt = 0;
while(t % pp[i] == 0) ++ cnt, t/=pp[i];
if(cnt) ans *= (2*cnt+1);
if(t == 1) break;
}
if(t > 1) ans *= 3;
printf("Case %d: %lld
", ++cas, (ans+1)/2);
}
return 0;
}
CF 455A div1 1600
一道水题居然wa了3发
#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long LL;
const int MXN = 1e6 + 7;
const int mod = 998244353;
int n;
LL dp[MXN][2];
int ar[MXN], is[MXN];
int main() {
#ifndef ONLINE_JUDGE
freopen("./文档/acm/in.txt", "r", stdin);
printf("*Cwolf9*
");
//freopen("out.txt", "w", stdout);
#endif
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]), ++ is[ar[i]];
dp[1][0] = 0; dp[1][1] = is[1];
for(int i = 2; i <= 100000; ++i) {
dp[i][1] = max(dp[i-1][1], dp[i-1][0] +(LL)is[i]*i);
dp[i][0] = max(dp[i-1][1], dp[i-1][0]);
}
printf("%lld
", max(dp[100000][0], dp[100000][1]));
return 0;
}
CF 431C div2 1600
1600分的题好水啊
dp[i][j]表示已经获得了i分，最高分是j分的方案数。
数据范围只有100。暴力就行了。
#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long LL;
const int MXN = 1e3 + 7;
const int mod = 998244353;
const int MOD = 1000000007;
int n;
int k, d;
LL dp[MXN][MXN];
int main() {
#ifndef ONLINE_JUDGE
freopen("./文档/acm/in.txt", "r", stdin);
printf("*Cwolf9*
");
//freopen("out.txt", "w", stdout);
#endif
scanf("%d%d%d", &n, &k, &d);
for(int i = 1; i <= k; ++i) dp[i][i] = 1;
for(int i = 2; i <= n; ++i) {
for(int j = 1; j <= min(i, k); ++j) {
for(int h = 1; h < j; ++h) dp[i][j] += dp[i-h][j] + dp[i-j][h], dp[i][j] %= MOD;
dp[i][j] = (dp[i-j][j]+dp[i][j]) % MOD;
}
}
LL ans = 0;
for(int i = d; i <= k; ++i) ans = (ans + dp[n][i]) % MOD;
printf("%lld
", ans);
return 0;
}
CF 431D div2 2200
sb数位dp
和UVALive - 3675这题的难度没得比
读错题wa了一发
#include<bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long LL;
const int MXN = 1e3 + 7;
const int mod = 998244353;
const int MOD = 1000000007;
int n;
LL m; int k;
int ar[MXN];
LL dp[70][2][70];//第i位为j，后i-1位共有k个1的方案数
LL dfs(int pos,int cur,bool lead,bool limit,int cnt) {
if(pos == -1) return cnt == k;
if(cnt > k) return 0;
if(!limit&&!lead&&dp[pos][cur][k-cnt]!=-1) return dp[pos][cur][k-cnt];
int up = limit? ar[pos]: 1;
LL sum = 0;
for(int i = 0; i <= up; ++i) {
sum += dfs(pos-1,i,lead&&i==0,limit&&i==ar[pos],cnt+(i==1));
}
if(!limit&&!lead) dp[pos][cur][k-cnt] = sum;
return sum;
}
LL gao(LL x) {
if(x == 0) return 0;
int pos = 0;
while(x) {
ar[pos++] = x % 2;
x /= 2;
}
return dfs(pos-1, 0, 1, 1, 0);
}
LL check(LL mid) {
return gao(2*mid) - gao(mid);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("./文档/acm/in.txt", "r", stdin);
printf("*Cwolf9*
");
//freopen("out.txt", "w", stdout);
#endif
memset(dp, -1, sizeof(dp));
scanf("%lld%d", &m, &k);
LL L = 1, R =1000000000000000000, ans = 1, mid;
while(L <= R) {
mid = (L + R) >> 1;
LL tmp = check(mid);
if(tmp == m) {
ans = mid; break;
}
if(tmp < m) L = mid + 1;
else R = mid - 1;
}
printf("%lld
", ans);
return 0;
}
CF 118D div2 1800
有(n)个字符(1)，(m)个字符(2)，问这些能组成多少个合法的长度(n+m)的字符串？
有超过(k1)个连续的字符(1)或超过(k2)个连续的字符(2)的字符串为不合法的字符串。
(dp[i][j][0][k])表示已经使用了(i)个字符(1)和(j)个字符(2)最后是连续的(k)个字符(1)的合法字符串的数量
(dp[i][j][1][k])表示已经使用了(i)个字符(1)和(j)个字符(2)最后是连续的(k)个字符(2)的合法字符串的数量
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int MXN = 2e5 + 3;
const int mod = 100000000;
int n, m;
int p, q;
int dp[105][105][2][105];
int main() {
scanf("%d%d", &n, &m);
scanf("%d%d", &p, &q);
dp[0][0][0][0] = dp[0][0][1][0] = 1;
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= m; ++j) {
if(i + j == 0) continue;
for(int k = 2; k <= min(i, p); ++k) {
if(i) dp[i][j][0][k] = (dp[i][j][0][k] + dp[i-1][j][0][k-1]) % mod;
if(j) dp[i][j][1][1] = (dp[i][j][1][1] + dp[i][j-1][0][k]) % mod;
}
for(int k = 2; k <= min(j, q); ++k) {
if(i) dp[i][j][0][1] = (dp[i][j][0][1] + dp[i-1][j][1][k]) % mod;
if(j) dp[i][j][1][k] = (dp[i][j][1][k] + dp[i][j-1][1][k-1]) % mod;
}
if(i) dp[i][j][0][1] = (dp[i][j][0][1] + dp[i-1][j][1][1]) % mod;
if(j) dp[i][j][1][1] = (dp[i][j][1][1] + dp[i][j-1][0][1]) % mod;
if(i) dp[1][0][0][1] = 1;
if(j) dp[0][1][1][1] = 1;
}
}
int ans = 0;
for(int i = 1; i <= p; ++i) ans = (ans + dp[n][m][0][i]) % mod;
for(int i = 1; i <= q; ++i) ans = (ans + dp[n][m][1][i]) % mod;
printf("%d
", ans);
return 0;
}
HDU4089 概率dp 迭代
- Activation failed
- Connection failed
- Activation succeeded
- Service unavailable
dp[i][j]: server down and the number of people before him is less than k.
注意要迭代算出dp[i][i]!!!
要特判，因为有可能p[3]特别小其实答案应该是0，但是p[0]特别大，导致p[1],p[2],p[3]转换后较为平均，会算出一个不合理的答案。
#include<bits/stdc++.h>
#define o2(x) (x)*(x)
#define rep(i, s, t) for(int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(int i = (s), LIM=(t); i >= LIM; --i)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int mod = 1000000007;
const int INF = 0x3f3f3f3f;
const int MXN = 2e3 + 7;
int n, m, k;
double pb[5], dp[2][MXN];
int main() {
#ifndef ONLINE_JUDGE
freopen("D:in.in", "r", stdin);
freopen("D:out.out", "w", stdout);
#endif
while(~scanf("%d%d%d", &n, &m, &k)) {
rep(i, 0, 4) scanf("%lf", pb + i);
if(pb[3] < 1e-8) {
printf("0.00000
");
continue;
}
rep(i, 1, 4) pb[i] = pb[i]/(1 - pb[0]);
memset(dp, 0, sizeof(dp));
dp[1][1] = pb[3] / (1 - pb[1]);
int p = 1;
rep(i, 2, n + 1) {
double tmp1 = 0;
double tmp2 = 1;
per(j, i, 2) {
tmp1 += tmp2 * ((j <= k?pb[3]:0) + pb[2] * dp[p][j-1]);
tmp2 *= pb[1];
}
tmp1 += tmp2 * pb[3];
tmp2 *= pb[1];
dp[!p][i] = tmp1 / (1 - tmp2);
rep(j, 1, i) {
if(j == 1) {
dp[!p][j] = pb[3] + pb[1] * dp[!p][i];
}else if(j <= k) {
dp[!p][j] = pb[3] + pb[1] * dp[!p][j-1] + pb[2] * dp[p][j-1];
}else {
dp[!p][j] = pb[1] * dp[!p][j-1] + pb[2] * dp[p][j-1];
}
}
p = !p;
}
printf("%.5f
", dp[p][m]);
}
return 0;
}
ZOJ3329 概率dp 迭代
dp[i]=∑(pkdp[i+k])+dp[0]p0+1
迭代求出答案
dp[i] = cnt[i] + num[i] * dp[0]
dp[0] = cnt[0] + num[0] * dp[0]
ans = dp[0]
#include<bits/stdc++.h>
#define o2(x) (x)*(x)
#define rep(i, s, t) for(int i = (s), LIM=(t); i < LIM; ++i)
#define per(i, s, t) for(int i = (s), LIM=(t); i >= LIM; --i)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int mod = 1000000007;
const int INF = 0x3f3f3f3f;
const int MXN = 2e3 + 7;
int n, m, k;
int up[3], aim[3];
long double cnt[MXN], num[MXN];
/*
dp[i]=∑(pk*dp[i+k])+dp[0]*p0+1
迭代求出答案
dp[i] = cnt[i] + num[i] * dp[0]
dp[0] = cnt[0] + num[0] * dp[0]
ans = dp[0]
*/
int main() {
#ifndef ONLINE_JUDGE
freopen("D:in.in", "r", stdin);
freopen("D:out.out", "w", stdout);
#endif
int tim;
scanf("%d", &tim);
while(tim --) {
scanf("%d", &n);
rep(i, 0, 3) scanf("%d", &up[i]);
rep(i, 0, 3) scanf("%d", &aim[i]);
rep(i, 0, 1000) cnt[i] = num[i] = 0;
per(i, n, 0) {
cnt[i] = 1;
rep(a, 1, up[0] + 1) {
rep(b, 1,up[1] + 1) {
rep(c, 1, up[2] + 1) {
if(a == aim[0] && b == aim[1] && c == aim[2])
num[i] += 1.0 / (up[0] * up[1] * up[2]);
else {
cnt[i] += cnt[i + a + b + c] / (up[0] * up[1] * up[2]);
num[i] += num[i + a + b + c] / (up[0] * up[1] * up[2]);
}
}
}
}
}
printf("%.15Lf
", cnt[0] / (1 - num[0]));
}
return 0;
}
HDU4035 树上概率DP 迭代法
https://www.cnblogs.com/kuangbin/archive/2012/10/02/2710606.html
点我点我
题意：
有n(1e4)个房间，由n-1条隧道连通起来，实际上就形成了一棵树.
从结点1出发，开始走，在每个结点i都有3种可能：
1.被杀死，回到结点1处（概率为ki）
2.找到出口，走出迷宫 （概率为ei）
3.和该点相连有m条边，随机走一条
4.(k1=e1=0)
求：走出迷宫所要走的边数的期望值。
解析：
列出方程，对方程进行化简，迭代递推。
因为每个节点还可能从父节点转移过来，所以需要记录从父节点转移过来的系数，从上递推
的时候刚好可以化简掉。
1号节点：
(E[1] = A1*E[1] + B1*0 + C1;)
(ans = E[1] = C1/(1 - A1);)
叶子结点：
(E[i] = ki*E[1] + ei*0 + (1-ki-ei)*(E[father[i]] + 1);)
(= ki*E[1] + (1-ki-ei)*E[father[i]] + (1-ki-ei);)
非叶子结点：（m为与结点相连的边数）
(E[i] = ki*E[1] + ei*0 + (1-ki-ei)/m*( E[father[i]]+1 + ∑( E[child[i]]+1 ) );)
(= ki*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei)/m*∑(E[child[i]]) + (1-ki-ei);)
令：(E[i] = Ai*E[1] + Bi*E[father[i]] + Ci;)
(∑(E[child[i]])=∑Aj*E[1]+∑Bj*E[i]+∑Cj)
(E[i]=ei*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei)/m*(∑Aj*E[1]+∑Bj*E[i]+∑Cj) + (1-ki-ei))
((1-(1-ki-ei)/m*∑Bj)E[i]=(ki+(1-ki-ei)/m*∑Aj)*E[1] + (1-ki-ei)/m*E[father[i]]+(1-ki-ei)/m*∑Cj+(1-ki-ei))
从叶子到根推出ABC系数即可，当A[1]趋近于1则无解。
卡精度。
AC_CODE
点我点我