【开坑】codeforces水题泛做
关于一些水题，思维题，套路dp菜得不行，于是点了个dp-tag，开了这个坑
目前困于水平只限制了1k4到1k8分数段的题，按过题人数降序，1k6+就很虐我了估计放开上限到2k+就受不了了QAQ
由于cf的tag机制，混了一些奇怪的东西不太像dp的题进来，能练手的也尽量写了
总之，为了队友，为了湘潭邀请赛和女生赛，赶紧提高到能独立完成gym3x的程度吧（还是太菜了QAQ
455A - 删a[k]会删除所有a[k]-1和a[k]+1，获得a[k]
dp[i]为数字1-i能获得的最大价值
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5#define LL long long
6#define INF 0x3f3f3f3f
7#define debug(x) cout << #x << " = " << x << endl;
8usingnamespace std;
9
10constint mx = 1e5;
11 LL dp[mx+7];
12int vis[mx+10];
13
14int main(){
15int n, a, m = 0;
16 scanf("%d", &n);
17for (int i = 1; i <= n; i++) {
18 scanf("%d", &a);
19 m = max(m, a);
20 vis[a]++;
21 }
22 dp[1] = vis[1];
23for (int i = 2; i <= m; i++){
24 dp[i] = max(dp[i-1], dp[i-2]+1ll*vis[i]*i);
25 }
26 printf("%lld\n", dp[m]);
27return0;
28 }
View Code
466C - 数组划分成相等三段的方案数
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <vector>
6#define LL long long
7#define INF 0x3f3f3f3f
8#define debug(x) cout << #x << " = " << x << endl;
9usingnamespace std;
10
11constint mx = 5e5+7;
12LL sum[mx];
13
14int main(){
15int n, c;
16 scanf("%d", &n);
17for (int i = 1; i <= n; i++){
18 scanf("%d", &c);
19 sum[i] = sum[i-1]+c;
20 }
21 vector<int> a, b;
22for (int i = 1; i < n; i++){
23if (sum[i]*3 == sum[n]) a.push_back(i);
24if (sum[i]*3 == sum[n]*2) b.push_back(i);
25 }
26 LL ans = 0;
27for (int i = 0; i < a.size(); i++){
28int k = upper_bound(b.begin(), b.end(), a[i])-b.begin();
29 ans += b.size()-k;
30 }
31 printf("%lld\n", ans);
32return0;
33 }
View Code
698A - 每天能做事或者休息，两天不做一样的事，最小休息天数
dp[i][0/1/2]当天做的事/休息
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5#define LL long long
6#define INF 0x3f3f3f3f
7#define debug(x) cout << #x << " = " << x << endl;
8usingnamespace std;
9
10constint mx = 110;
11int dp[mx][3];
12
13int main(){
14int n, a;
15 scanf("%d", &n);
16 memset(dp, INF, sizeof dp);
17//dp[i][0/1/2]
18 dp[0][0] = 0;
19for (int i = 1; i <= n; i++) {
20 scanf("%d", &a);
21 dp[i][0] = min(dp[i-1][0], min(dp[i-1][1], dp[i-1][2]))+1;
22if (!a) continue;
23if (a != 2) dp[i][2] = min(dp[i-1][0], dp[i-1][1]);
24if (a != 1) dp[i][1] = min(dp[i-1][0], dp[i-1][2]);
25 }
26 printf("%d\n", min(dp[n][0], min(dp[n][1], dp[n][2])));
27return0;
28 }
View Code
545C - n棵树砍了往左或者往右倒，不能倒在一起，最大砍伐数
dp[i][0/1]当前往左或者往右倒
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <vector>
6#define LL long long
7#define INF 0x3f3f3f3f
8#define debug(x) cout << #x << " = " << x << endl;
9usingnamespace std;
10
11constint mx = 1e5+7;
12LL x[mx], h[mx];
13int dp[mx][2];
14
15int main(){
16int n;
17 scanf("%d", &n);
18for (int i = 1; i <= n; i++) scanf("%lld%lld", &x[i], &h[i]);
19 dp[1][0] = 1, dp[1][1] = x[1]+h[1] < x[2];
20 x[n+1] = 1e18;
21for (int i = 2; i <= n; i++){
22 dp[i][0] = max(dp[i][0], dp[i-1][0]+(x[i]-h[i] > x[i-1]));
23 dp[i][0] = max(dp[i][0], dp[i-1][1]+(x[i]-h[i] > x[i-1]+h[i-1]));
24 dp[i][1] = max(dp[i][1], dp[i-1][1]+(x[i-1]+h[i-1] < x[i] && x[i]+h[i] < x[i+1]));
25 dp[i][1] = max(dp[i][1], dp[i-1][0]+(x[i]+h[i] < x[i+1]));
26 }
27 printf("%d\n", max(dp[n][0], dp[n][1]));
28return0;
29 }
View Code
431C - k叉树边权1-k，和为n且有一条不小于d的边权的路径数
背包，dp[i][0/1]边权为i，最大值是否大于d
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <vector>
6#define LL long long
7#define INF 0x3f3f3f3f
8#define debug(x) cout << #x << " = " << x << endl;
9usingnamespace std;
10
11constint mx = 110;
12constint mod = 1e9+7;
13 LL dp[mx][2];
14
15int main(){
16int n, k, d;
17 scanf("%d%d%d", &n, &k, &d);
18//dp[w][0/1]
19 dp[0][0] = 1;
20for (int i = 1; i <= n; i++){
21for (int j = 1; j <= k; j++){
22if (i < j) break;
23 dp[i][1] += dp[i-j][1];
24 dp[i][(j >= d)] += dp[i-j][0];
25 dp[i][0] %= mod, dp[i][1] %= mod;
26 }
27 }
28 printf("%lld\n", dp[n][1]);
29return0;
30 }
View Code
474D - 只能吃1朵红花，或者k的倍数朵白花
。。。居然跟选拔赛我出的题一模一样，背包
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5#define LL long long
6#define INF 0x3f3f3f3f
7#define debug(x) cout << #x << " = " << x << endl;
8usingnamespace std;
9
10constint mx = 1e5+7;
11constint mod = 1e9+7;
12LL sum[mx], dp[mx];
13
14int main(){
15int t, k, a, b;
16 scanf("%d%d", &t, &k);
17//dp[i] = dp[i-1]+dp[i-k]
18 dp[0] = 1;
19for (int i = 1; i < k; i++)
20 dp[i] = 1, sum[i] = sum[i-1]+1;
21for (int i = k; i < mx; i++)
22 dp[i] = (dp[i-1]+dp[i-k])%mod, sum[i] = (sum[i-1]+dp[i])%mod;
23while (t--){
24 scanf("%d%d", &a, &b);
25 printf("%lld\n", (sum[b]-sum[a-1]+mod)%mod);
26 }
27return0;
28 }
View Code
414B - 构造1-n内长为k，后一个数是前一个数倍数的数组方案
dp[i][j]表示前i个数最后一位放j
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <vector>
6#define LL long long
7#define INF 0x3f3f3f3f
8#define debug(x) cout << #x << " = " << x << endl;
9usingnamespace std;
10
11constint mx = 2010;
12constint mod = 1e9+7;
13LL dp[mx][mx];
14
15int main(){
16int n, k;
17 scanf("%d%d", &n, &k);
18for (int i = 1; i <= n; i++) dp[1][i] = 1;
19for (int i = 2; i <= k; i++){
20for (int j = 1; j <= n; j++){
21for (int s = 1; s*s <= j; s++){
22if (j % s != 0) continue;
23 dp[i][j] += dp[i-1][s];
24if (s*s != j) dp[i][j] += dp[i-1][j/s];
25 dp[i][j] %= mod;
26//cout << i << " " << j << " " << s << " " << dp[i][j] << endl;
27 }
28 }
29 }
30 LL ans = 0;
31for (int i = 1; i <= n; i++)
32 ans = (ans + dp[k][i]) % mod;
33 printf("%lld\n", ans);
34return0;
35 }
View Code
166E - 四面体走n步回到原点的方案
dp[i][j] 第i步在j点，16n滚动数组卡着时限过，有递推公式n解
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <vector>
6#define LL long long
7#define INF 0x3f3f3f3f
8#define debug(x) cout << #x << " = " << x << endl;
9usingnamespace std;
10
11constint mod = 1e9+7;
12 LL dp[2][4];
13
14void upd(int c, int t){
15for (int i = 0; i < 4; i++){
16if (i == c) continue;
17 dp[t^1][c] += dp[t][i];
18 dp[t^1][c] %= mod;
19 }
20}
21
22int main(){
23int n, t = 1;
24 scanf("%d", &n);
25 dp[1][0] = 1;
26for (int i = 1; i <= n; i++){
27for (int j = 0; j < 4; j++) upd(j, t);
28 memset(dp[t], 0, sizeof dp[t]);
29 t ^= 1;
30 }
31 printf("%lld\n", dp[t][0]);
32return0;
33 }
View Code
706C - n个字符串可以反转，改成字典序的花费
dp[i][0/1] 前i个字符串当前反/不反
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <vector>
6#define LL long long
7#define INF 0x3f3f3f3f3f3f3f3f
8#define debug(x) cout << #x << " = " << x << endl;
9usingnamespace std;
10
11constint mx = 1e5+7;
12struct node{
13int num;
14string a, b;
15}s[mx];
16 LL dp[mx][2];
17
18int main(){
19int n;
20 cin >> n;
21for (int i = 1; i <= n; i++) cin >> s[i].num;
22for (int i = 1; i <= n; i++){
23 cin >> s[i].a;
24 s[i].b.assign(s[i].a.rbegin(), s[i].a.rend());
25 dp[i][0] = dp[i][1] = INF;
26 }
27 dp[1][0] = 0, dp[1][1] = s[1].num;
28for (int i = 2; i <= n; i++){
29if (s[i].a >= s[i-1].a) dp[i][0] = min(dp[i][0], dp[i-1][0]);
30if (s[i].a >= s[i-1].b) dp[i][0] = min(dp[i][0], dp[i-1][1]);
31if (s[i].b >= s[i-1].a) dp[i][1] = min(dp[i][1], dp[i-1][0]+s[i].num);
32if (s[i].b >= s[i-1].b) dp[i][1] = min(dp[i][1], dp[i-1][1]+s[i].num);
33 }
34 LL ans = min(dp[n][0], dp[n][1]);
35 printf("%lld\n", ans == INF ? -1 : ans);
36return0;
37 }
View Code
676C - 长度为n的ab字符串可以改k个字符，最长连续相同段
前缀和，二分左端点
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <vector>
6#define LL long long
7#define INF 0x3f3f3f3f
8#define debug(x) cout << #x << " = " << x << endl;
9usingnamespace std;
10
11constint mx = 1e5+7;
12char s[mx];
13int sum[2][mx];
14
15int main(){
16int n, k;
17 scanf("%d%d%s", &n, &k, s+1);
18for (int i = 1; i <= n; i++){
19 sum[0][i] = sum[0][i-1]+(s[i] == 'a');
20 sum[1][i] = sum[1][i-1]+(s[i] == 'b');
21 }
22int ans = 0;
23for (int i = 1; i <= n; i++){
24int x = upper_bound(sum[0]+1, sum[0]+n+1, sum[0][i]+k-(s[i]=='a'))-sum[0]-1;
25 ans = max(ans, x-i+1);
26 x = upper_bound(sum[1]+1, sum[1]+n+1, sum[1][i]+k-(s[i]=='b'))-sum[1]-1;
27 ans = max(ans, x-i+1);
28 }
29 printf("%d\n", ans);
30return0;
31 }
View Code
446A - n个数能改变一个，求最长递增子串
搞一下左边有多少比它小的，右边有多少比它大的枚举
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <vector>
6#define LL long long
7#define INF 0x3f3f3f3f
8#define debug(x) cout << #x << " = " << x << endl;
9usingnamespace std;
10
11constint mx = 1e5+7;
12int a[mx], l[mx], r[mx];
13
14int main(){
15int n;
16 scanf("%d", &n);
17for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
18if (n <= 2){
19 printf("%d\n", n);
20return0;
21 }
22for (int i = 2; i <= n; i++){
23if (a[i] > a[i-1]) l[i] = l[i-1]+1;
24else l[i] = 0;
25 }
26for (int i = n-1; i >= 1; i--) {
27if (a[i] < a[i+1]) r[i] = r[i+1]+1;
28else r[i] = 0;
29 }
30int ans = 0;
31 ans = max(ans, l[n-1]+2);
32 ans = max(ans, r[2]+2);
33for (int i = 2; i < n; i++){
34int sum = max(l[i-1], r[i+1]);
35if (a[i-1]+1 < a[i+1]) sum += min(l[i-1], r[i+1])+1;
36 ans = max(ans, sum+2);
37 }
38 printf("%d\n", ans);
39return0;
40 }
View Code
2019.3.14 先回去了，今天没发现很有收获的题，水题就必须每天多写几题吧
467C - 用k个长度为m不重合的区间覆盖n的数组，求最大价值
dp[i][j] 前i个数字用了j个区间
Java课上皮了一下偷偷刷题，代码没啥区别
1import java.util.Scanner; 2 3publicclass Main {
4publicstaticvoid main(String[] args){
5finalint MX = 5010;
6 Scanner sc = new Scanner(System.in);
7int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt(), a;
8long[] sum = newlong[MX];
9for (int i = 1; i <= n; i++){
10 a = sc.nextInt();
11 sum[i] = sum[i-1]+a;
12 }
13long[][] dp = newlong[MX][MX];
14for (int i = 1; i <= n; i++){
15for (int j = 1; j <= k; j++){
16 dp[i][j] = dp[i-1][j];
17if (i >= m)
18 dp[i][j] = Math.max(dp[i][j], dp[i-m][j-1]+sum[i]-sum[i-m]);
19 }
20 }
21 System.out.println(dp[n][k]);
22 }
23 }
View Code
118D - 1有n个，2有m个，1最多连续放a个，2最多连续放b个
dp[i][j][0/1] 1有i个2有j个，最后一个是1/2的方案数，取模坑了一发。。
一开始状态定义对了，后来某个地方写搓了让我误以为状态是错的。。。最近几题几乎都是无脑直觉定状态居然还一路对过来了qwq
还是畏难情绪太严重，其实这些都是水题的。。。开上限到2k了
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <vector>
6#define LL long long
7#define INF 0x3f3f3f3f
8#define debug(x) cout << #x << " = " << x << endl;
9usingnamespace std;
10
11constint mod = 1e8;
12constint mx = 110;
13 LL dp[mx][mx][2];
14
15int main(){
16int n, m, a, b;
17 scanf("%d%d%d%d", &n, &m, &a, &b);
18for (int i = 0; i <= a; i++) dp[i][0][0] = 1;
19for (int i = 0; i <= b; i++) dp[0][i][1] = 1;
20for (int i = 1; i <= n; i++){
21for (int j = 1; j <= m; j++){
22for (int k = 1; k <= a && i-k >= 0; k++){
23 dp[i][j][0] += dp[i-k][j][1];
24 dp[i][j][0] %= mod;
25 }
26for (int k = 1; k <= b && j-k >= 0; k++){
27 dp[i][j][1] += dp[i][j-k][0];
28 dp[i][j][1] %= mod;
29 }
30 }
31 }
32 printf("%lld\n", (dp[n][m][0]+dp[n][m][1])%mod);
33return0;
34 }
View Code
788A - dp[i][0/1]表示选第i个数，是奇数/偶数项的最大值
1 #include <bits/stdc++.h> 2#define LL long long
3#define INF 0x3f3f3f3f
4#define INFLL 0x3f3f3f3f3f3f3f3f
5#define debug(x) cout << #x << " = " << x << endl;
6#define lid id << 1
7#define rid id << 1 | 1
8usingnamespace std;
9
10constint mx = 1e5+7;
11int a[mx];
12 LL dp[mx][2];
13
14int main(){
15int n;
16 scanf("%d", &n);
17for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
18for (int i = 1; i < n; i++) a[i] = abs(a[i]-a[i+1]);
19 LL ans = 0;
20for (int i = 1; i < n; i++){
21 dp[i][0] = max(dp[i][0], dp[i-1][1]+a[i]);
22 dp[i][1] = max(dp[i][1], dp[i-1][0]-a[i]);
23 ans = max(ans, max(dp[i][0], dp[i][1]));
24 }
25 printf("%lld\n", ans);
26return0;
27 }
View Code
534B - 初速度，加速度和末速度求最大位移
dp[i][j]第i时刻速度为j
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5#define LL long long
6#define INF 0x3f3f3f3f
7#define debug(x) cout << #x << " = " << x << endl;
8usingnamespace std;
9
10constint mx = 110;
11int dp[mx][mx*10];
12
13int main(){
14int vl, vr, t, d;
15 scanf("%d%d%d%d", &vl, &vr, &t, &d);
16//dp[i][j] = max(dp[i-1][k] + k)
17 memset(dp, -1, sizeof dp);
18 dp[1][vl] = vl;
19for (int i = 1; i <= t; i++){
20for (int j = 0; j <= 1000; j++){
21if (dp[i][j] == -1) continue;
22for (int k = max(0, j-d); k <= j+d; k++)
23 dp[i+1][k] = max(dp[i+1][k], dp[i][j]+k);
24 }
25 }
26 printf("%d\n", dp[t][vr]);
27return0;
28 }
View Code
567C - 公比为k的等比数列数量
k定下来就可以map暴力搞
1 #include <bits/stdc++.h> 2#define LL long long
3#define INF 0x3f3f3f3f
4#define INFLL 0x3f3f3f3f3f3f3f3f
5#define debug(x) cout << #x << " = " << x << endl;
6usingnamespace std;
7
8constint mx = 1e5+7;
9 map<int, LL> dp[4];
10
11int main(){
12int n, k, a;
13 scanf("%d%d", &n, &k);
14 LL ans = 0;
15//dp[i][j]第i-1项,数字为j
16for (int i = 1; i <= n; i++){
17 scanf("%d", &a);
18if (a % k == 0){
19 ans += dp[2][a/k];
20 dp[2][a] += dp[1][a/k];
21 }
22 dp[1][a]++;
23 }
24 printf("%lld\n", ans);
25return0;
26 }
View Code
553A - 组合数 这里有个线性推逆元的方法
1 #include <bits/stdc++.h> 2#define LL long long
3#define INF 0x3f3f3f3f
4#define INFLL 0x3f3f3f3f3f3f3f3f
5#define debug(x) cout << #x << " = " << x << endl;
6usingnamespace std;
7
8constint mod = 1e9+7;
9constint mx = 1e6;
10int a[1010];
11 LL fac[mx+5], inv[mx+5];
12
13void init(){
14 fac[0] = 1;
15for (int i = 1; i <= mx; i++) fac[i] = fac[i-1]*i%mod;
16 inv[1] = 1;
17for (int i = 2; i <= mx; i++) inv[i] = mod-(mod/i)*inv[mod%i]%mod;
18 inv[0] = 1;
19for (int i = 1; i <= mx; i++) inv[i] = inv[i]*inv[i-1]%mod;
20}
21
22 LL C(int n, int m){
23return fac[n]*inv[m]%mod*inv[n-m]%mod;
24}
25
26int main(){
27 init();
28int n, sum = 0;
29 scanf("%d", &n);
30for (int i = 1; i <= n; i++) {
31 scanf("%d", &a[i]);
32 sum += a[i];
33 }
34 LL ans = 1;
35for (int i = n; i >= 1; i--){
36 ans = ans*C(sum-1, a[i]-1)%mod;
37 sum -= a[i];
38 }
39 printf("%lld\n", ans);
40return0;
41 }
View Code
607A - dp[i]表示i后面的全部破坏,前面会被破坏的数量
1 #include <bits/stdc++.h> 2#define LL long long
3#define INF 0x3f3f3f3f
4#define INFLL 0x3f3f3f3f3f3f3f3f
5#define debug(x) cout << #x << " = " << x << endl;
6usingnamespace std;
7
8constint mx = 1e5+7;
9struct node{
10int x, y;
11booloperator < (const node& c) const {
12return x < c.x;
13 }
14}a[mx];
15int dp[mx];
16
17int main(){
18int n;
19 scanf("%d", &n);
20for (int i = 1; i <= n; i++) {
21 scanf("%d%d", &a[i].x, &a[i].y);
22 }
23 sort(a+1, a+n+1);
24int ans = INF;
25for (int i = 1; i <= n; i++){
26int k = lower_bound(a+1, a+n+1, node{a[i].x-a[i].y, 0})-a-1;
27 dp[i] = dp[k]+i-k-1;
28 ans = min(ans, dp[i]+n-i);
29 }
30 printf("%d\n", ans);
31return0;
32 }
View Code
603A - dp[i][0/1/2][0/1]表示前i个字符翻转的状态为j数字为k时的最大长度
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5 #include <map>
6#define LL long long
7#define INF 0x3f3f3f3f
8#define debug(x) cout << #x << " = " << x << endl;
9usingnamespace std;
10
11constint mx = 1e5+7;
12char s[mx];
13int dp[mx][3][2];
14
15int main(){
16int n, ans = 0;
17 scanf("%d%s", &n, s+1);
18for (int i = 1; i <= n; i++){
19int c = s[i]-'0';
20 memcpy(dp[i], dp[i-1], sizeof dp[i]);
21for (int j = 0; j < 3; j++){
22for (int k = 0; k < 2; k++) {
23if (k != c)
24 dp[i][j][c] = max(dp[i][j][c], dp[i-1][j][k]+1);
25elseif (j)
26 dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k]+1);
27 }
28 }
29 }
30for (int i = 0; i < 3; i++)
31for (int j = 0; j < 2; j++)
32 ans = max(ans, dp[n][i][j]);
33 printf("%d\n", ans);
34return0;
35 }
View Code
577B - 抽屉原理，然后就是n方的裸dp，滚动数组（感觉memcpy的方法真的好写
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5#define LL long long
6#define INF 0x3f3f3f3f
7#define debug(x) cout << #x << " = " << x << endl;
8usingnamespace std;
9
10constint mx = 1e6+7;
11int dp[2][1010];
12int a[mx];
13
14int main(){
15int n, m;
16 scanf("%d%d", &n, &m);
17for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
18if (n >= m){
19 printf("YES\n");
20return0;
21 }
22for (int i = 1; i <= n; i++){
23for (int j = 0; j < m; j++) dp[1][j] = 0;
24 dp[1][a[i]%m] = 1;
25for (int j = 0; j < m; j++){
26if (dp[1][0]) break;
27if (a[i] % m == j) continue;
28 dp[1][j] = max(dp[0][j], dp[0][(j-a[i]%m+m)%m]);
29 }
30 memcpy(dp[0], dp[1], sizeof dp[0]);
31 }
32 printf("%s\n", dp[0][0] ? "YES" : "NO");
33return0;
34 }
View Code
264B - 设dp[i]为结尾的数字质因数有i的最大长度（可以看做是对于每一位ai的质因数做LIS
1 #include <cstdio> 2 #include <cstring>
3 #include <iostream>
4 #include <algorithm>
5#define LL long long
6#define INF 0x3f3f3f3f
7#define debug(x) cout << #x << " = " << x << endl;
8usingnamespace std;
9
10constint mx = 1e5+7;
11int a[mx], prime[mx];
12int dp[mx];
13bool vis[mx];
14int tot = 0;
15
16void init(int n){
17 vis[1] = 1;
18for (int i = 2; i <= n; i++){
19if (!vis[i]) prime[++tot] = i;
20for (int j = 1; j <= tot && 1ll*i*prime[j] <= n; j++){
21 vis[i*prime[j]] = 1;
22if (i % prime[j] == 0) break;
23 }
24 }
25}
26
27int main(){
28 init(100000);
29int n, x, ans = 0;
30 scanf("%d", &n);
31for (int i = 1; i <= n; i++) {
32 scanf("%d", &a[i]);
33if (n == 1){
34 printf("1\n");
35return0;
36 }
37 x = a[i];
38int tmp = 0;
39for (int j = 1; j <= tot && j*j <= x; j++){
40if (x % prime[j] != 0) continue;
41while (x % prime[j] == 0) x /= prime[j];
42 tmp = max(tmp, dp[prime[j]]+1);
43 }
44if (x > 1) tmp = max(tmp, dp[x]+1);
45 x = a[i];
46for (int j = 1; j <= tot && j*j <= x; j++){
47if (x % prime[j] != 0) continue;
48while (x % prime[j] == 0) x /= prime[j];
49 dp[prime[j]] = tmp;
50 }
51if (x > 1) dp[x] = tmp;
52 ans = max(ans, tmp);
53 }
54 printf("%d\n", ans);
55return0;
56 }
View Code
225B- dp[i][j][0/1]表示前i列前面连续了j列相同,当前列是0/1的最小代价, 预处理代价然后刷表, 最后在合法范围内找答案
1 #include <bits/stdc++.h> 2#define INF 0x3f3f3f3f
3#define debug(x) cout << #x << " = " << x << endl;
4#define lid id << 1
5#define rid id << 1 | 1
6usingnamespace std;
7 typedef longlong LL;
8 typedef pair<int,int> pii;
9 typedef pair<double,double> pdd;
10
11constint mx = 1010;
12char s[mx];
13int a[mx], dp[mx][mx][2];
14
15int main(){
16int n, m, x, y;
17 scanf("%d%d%d%d", &n, &m, &x, &y);
18for (int i = 1; i <= n; i++){
19 scanf("%s", s+1);
20for (int j = 1; j <= m; j++)
21if (s[j] == '#') a[j]++;
22 }
23 memset(dp, INF, sizeof dp);
24 dp[1][1][0] = a[1];
25 dp[1][1][1] = n-a[1];
26for (int i = 1; i < m; i++){
27for (int j = 1; j <= y; j++){
28if (dp[i][j][0] != INF){
29if (j >= x) dp[i+1][1][1] = min(dp[i+1][1][1], dp[i][j][0] + n-a[i+1]);
30 dp[i+1][j+1][0] = min(dp[i+1][j+1][0], dp[i][j][0] + a[i+1]);
31 }
32if (dp[i][j][1] != INF){
33if (j >= x) dp[i+1][1][0] = min(dp[i+1][1][0], dp[i][j][1] + a[i+1]);
34 dp[i+1][j+1][1] = min(dp[i+1][j+1][1], dp[i][j][1] + n-a[i+1]);
35 }
36 }
37 }
38int ans = INF;
39for (int i = x; i <= y; i++){
40 ans = min(ans, dp[m][i][0]);
41 ans = min(ans, dp[m][i][1]);
42 }
43 printf("%d\n", ans);
44return0;
45 }
View Code
以上是 【开坑】codeforces水题泛做 的全部内容， 来源链接： utcz.com/z/509653.html
