數位DP專練

2022-09-22 20:33:07 字數 2692 閱讀 3293

數位dp專練

p4999 煩人的數學作業

直接數位dp,考慮前pos位,和值為sum,有無到極限(flag)

然後直接深搜

#include #include #include typedef long long ll;

const ll maxn = 1e6+10;

const ll mod = 1e9+7;

ll l, r, lim[20], cnt, f[20][200][2], t;

ll ask(ll);

ll dfs(ll, ll, bool);

int main()

return 0;

}ll ask(ll num)

ll dfs(ll pos, ll sum, bool flag)

f[pos][sum][flag] = ret % mod;

return ret;

}

p2602 zjoi2010數字計數

每一種數字單獨dp,記一下前導0,極限,和值,目前要求的數字和位置

#include #include #include using namespace std;

typedef long long ll;

const ll maxn = 1e6+10;

ll l, r, cnt, f[13][13][2][2], lim[100];

ll ask(ll, ll);

ll dfs(ll, ll, bool, bool, ll);

int main()

ll ask(ll num, ll d)

ll dfs(ll pos, ll sum, bool flag, bool zero, ll d)

f[pos][sum][flag][zero] = ret;

return ret;

}

p4124 cqoi2016手機號碼

直接dp,記錄上一位是啥,上上一位是啥,有無三連以及以上,極限,有無4,有無8。

#include #include #include using namespace std;

typedef long long ll;

const ll maxn = 1e6+10;

ll l, r, f[12][11][11][2][2][2][2], lim[maxn], cnt = 0;

ll ask(ll);

ll dfs(ll, ll, ll, ll, ll, ll, ll);

int main()

ll ask(ll num)

return ret;

}ll dfs(ll pos, ll a, ll b, ll c, ll flag, ll is4, ll is8)

f[pos][a][b][c][flag][is4][is8] = ret;

return ret;

}

p6218 usaco06nov round numbers s

轉化成2進位制,直接dp,注意前導0不能統計

#include #include #include using namespace std;

typedef long long ll;

const ll maxn = 1e6+10;

ll r, l, lim[65], f[65][65][65][2][2], cnt;

ll ask(ll);

ll dfs(ll, ll, ll, bool, bool);

int main()

ll ask(ll num)

ll dfs(ll pos, ll numz, ll numo, bool flag, bool zero)

f[pos][numz][numo][flag][zero] = ret;

return ret;

}

p6754 balticoi 2013 day1 palindrome-free numbers

直接數位dp,和萌數差不多。

也就是說,對於任意一個 \(a_i\) 只要 \(a_i \ne a_\) 或者 \(a_i \ne a_\) 它就不迴文(很好想)

#include #include #include using namespace std;

typedef long long ll;

const ll maxn = 1e6+10;

ll l, r, x, cnt, lim[20], f[21][2][2][11][11];

ll ask(ll);

ll dfs(ll, bool, bool, ll, ll);

int main()

ll ask(ll num)

ll dfs(ll pos, bool flag, bool zero, ll a, ll b)

f[pos][flag][zero][a][b] = ret;

return ret;

}

數位dp通解:

int dfs(int pos /*會對決策造成影響的東西,比如極限,前導0,當前和值,連續段等等*/) 

/*記憶化*/

return /*返回值*/

}