Codeforces DP1400 题 大赏
CF628B New Skateboard
大意
给定一个字符串，求其中能被4整除的字串数量。
思路
能被4整除的数字，其末两位数一定能被4整除。所以我们只需枚举末两位能被4整除的所有情况。对于每一个这样的两位数，其前面的所有组合都可以被4整除。而这两位数又分为两种情况：一种是个位数能被4整除。显然，这种情况意味着只能是这单个数字能被4整除，因为我们并不能保证前面的一位数字组合上这个数字能被4整除。另一种是两位数能被4整除，此时同样是任意的前面的数字与之组合能被4整除。下面给出这两种情况的解决方案：
- 如果当前数字本身就能被4整除，那么ans++；
- 如果（当前数字+前一个数字*10）能被4整除，则ans+=i（i为当前数字的下标）。因为对于每一个位置，都有其前面i个的连续组合。
那么只需利用for循环，遍历一遍字符串，就能轻易做出这道题目了。这道题并没有直接用上dp的状态转移方程，但确实有亿点点dp的推理思想。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <bits/stdc++.h>
using namespace std;
string s;
long long ans=0;
// int dp[300010];
//dp[i]表示到字符串的第i位为止能被4整除的字串的数量
bool check(int pos){
//获取s的第pos-1位到第pos位
string tmp = s.substr(pos-1,2);
//将tmp转成数字
int num = int(tmp[0]-'0')*10+int(tmp[1]-'0');
//如果num%4==0，则返回true
if(num%4==0) return true;
else return false;
}
int main(){
cin>>s;
int n=s.size();
for(int i=0;i<n;i++){
if(s[i]=='0'||s[i]=='4'||s[i]=='8'){
ans++;
// cout<<"ans1:"<<ans<<endl;
}
}
for(int i=1;i<n;i++){
if(check(i)){
ans+=i;
// cout<<"ans2:"<<ans<<endl;
}
}
cout<<ans<<endl;
return 0;
}
CF189A Cut Ribbon
大意：
给一长度为n的缎带，要求将其剪成若干长度为a,b,c的缎带，且缎带数量尽可能多。求这个最大值。注意，这里的缎带必须全部用a,b,c的长度剪且要刚好剪完。
思考
lls尝云：“dp的状态类似于dfs的参数。” 所以，如果直接定义dp的状态有困难，不如先思考用dfs如何解决这个问题。如果要用dfs解决这个问题，我们肯定要遍历选择到了第几个缎带，并枚举剪了几个当前的缎带。这样一来，就类似于完全背包，我们还能用一维数组空间压缩。只需输出dp[m]即可。
AC Code & Comments
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int dp[4010];//dp[i]表示装了i个空间的背包最大价值
int n,w[5];
int main(){
cin>>n>>w[1]>>w[2]>>w[3];
memset(dp,-1,sizeof(dp));
dp[0]=0;
for(int i=1;i<=3;i++){//枚举放第几个
for(int j=w[i];j<=n;j++){//枚举放的价值
//dp[j]由dp[j-w[i]]+w[i]算出来
if(dp[j-w[i]]!=-1)//如果dp[j-w[i]]没有计算过，则dp[j]也不会被计算
dp[j]=max(dp[j],dp[j-w[i]]+1);
}
}
cout<<dp[n]<<endl;
return 0;
}
CF1178B WOW Factor
翻译
给定一个只含“v”和"o"字符串s(长度最大为$10^6$) 求字符串中有多少个wow（一个“w”即为连续的两个“v”）。
分析
对于任意的一个wow，都是由vv...o...vv组成的。所以，当遇到vv时，就令vv的计数器++；当遇到o时，就令vvo的计数器+==vv；当再次遇到vv时，令vvovv的计数器+=vvo（这部操作可以合并到上面的vv，没有冲突）。其思路来源于下面这题：
</a></div> </div> </div> </div> </div>
代码
``` #include <bits/stdc++.h> using namespace std; long long v,vv,vvo,vvov,vvovv; string s; int main(){ cin>>s; for(int i=1;i<s.length();i++){ if(s[i]=='v'&&s[i-1]=='v'){ vvovv+=vvo; // vvov+=vvo; vv++; // v++; }else if(s[i]=='o'){ vvo+=vv; } // cout<<v<<" "<<vv<<" "<<vvo<<" "<<vvov<<" "<<vvovv<<endl; } cout<<vvovv; return 0; } ```CF691B s-palindrome
这道题和dp似乎没有半毛钱关系。略去。
CF698A Vacations
题目大意
Vasya有n天的假期 每天有四种选择：
0.在这一天，健身房关闭，比赛不进行；
1.在这一天，健身房关闭，比赛进行；
2.在这一天，健身房是开放的，比赛不进行；
3.在这一天，健身房是开放的，比赛是进行的。
在每一天，Vasya可以休息，比赛(如果在这一天进行)，或者做运动(如果健身房在这一天是开放的)。
但Vasya不想连续两天做同样的活动：这意味着，他不会连续两天做运动，也不会在连续两天写比赛。
找出Vasya休息的最少天数
解题过程
由题意不难得出，本题共有三个要素：
- 第几天
- 做什么
- 休息天数
其中，休息天数是所要求的答案。故dp的状态设计正好是两个：dp[i][j]表示第i天做j活动的最多工作（这里我们定义工作，便于理解，当然也可以最少休息天数）天数。j={1,2,3}，表示比赛，健身，与休息。
定义边界
根据我们的定义，当还未开始，即天数为0时，dp[0][j]=0，即没有休息。
状态转移方程
枚举每一天的情况。对于第i天，我们有下列转移方程：
- 当今天是比赛或休息，则明天可以是健身。否则明天健身的状态不存在。
- 当今天是健身或休息，则明天可以是比赛。否则明天比赛的状态不存在。
- 在任何情况下，明天都可以休息。
最终只需输出n-max(dp[n][1],max(dp[n][2],dp[n][3]))，即总天数减去最后一天是比赛、健身、休息中的工作最大值。
AC Code
``` #include <bits/stdc++.h> using namespace std; int n; int a[105]; int dp[105][4];//表示到第i天为止进行某一项活动的最多不休息天数 //1:健身 2:比赛 3:休息 int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } dp[0][1]=dp[0][2]=dp[0][3]=0; for(int i=1;i<=n;i++){ if(a[i]==2||a[i]==3){ dp[i][1]=max(dp[i-1][2],dp[i-1][3])+1; }else{ dp[i][1]=INT_MIN; } if(a[i]==1||a[i]==3){ dp[i][2]=max(dp[i-1][1],dp[i-1][3])+1; }else{ dp[i][2]=INT_MIN; } dp[i][3]=max(dp[i-1][1],max(dp[i-1][2],dp[i-1][3])); } cout<<n-max(dp[n][1],max(dp[n][2],dp[n][3])); return 0; } ```CF1195C Basketball Exercise
题目
给定一个 $2 \times n$ 的矩阵 $\{h\}$，现从中选择若干数，且任意两个数不上下或左右相邻，求这些数的和最大是多少？
思路
状态设计
显而易见，题目中有三个要素：第几列，选或不选选第几行，最大和。这里最大和是最终要求的答案，所以设计一个两维数组，dp[i][j]表示选到第i列、当前列选择的状态时的最大和。我们不妨定义：选第一行为1，第二行为2；不选为0。
边界
根据状态设计，可以看出，当还没选择，即选到第0列时，无论选择的状态为什么，最大和都为0。
状态转移方程
对于每一种不同的情况，我们都要分类讨论：
- 当这列不选，则可以从上一列的选第一行、选第二行或不选中转移，因为如果这列不选，无论如何都不会有相邻的。
- 当这列选第一行，则可以从上一列的选第二行或不选转移来。
- 第二行同理。
AC代码
``` #include <bits/stdc++.h> using namespace std; long long n; long long a[100005],b[100005]; long long dp[100005][3]; //dp[i]表示 选到第i列时 这次选第几行 (0代表这列没选) 和的最大值 int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ cin>>b[i]; } for(int i=1;i<=n;i++){ dp[i][0]=max(dp[i-1][1],max(dp[i-1][2],dp[i-1][0])); dp[i][1]=max(dp[i-1][0],dp[i-1][2])+a[i]; dp[i][2]=max(dp[i-1][0],dp[i-1][1])+b[i]; } cout<<max(dp[n][0],max(dp[n][1],dp[n][2])); return 0; } ```CF1245C Constanze's Machine
题目大意
给定一个字符串，规定可以将字符串中的连续两个nn变成m，也可以把连续两个vv变成w。当然也可以不变。现在请你求出有多少个可能得到的字符串。
解题
这道题可以换个角度思考，不用dp来解。
首先不难看出，我们需要找出几个连续的vv块和nn块，然后把它们的可能数乘起来，就是最终的答案。
那么现在的任务就转化为：给出v...v块和n...n块的长度，算出它的方案数。
我们再来回顾一下所谓方案数的定义（计算规则，这里就统一用字母v来举例了）：对任意的一串字母v...v，将其中每两个v变成一个w，求能有几种最终可能。
下面给出一个例子（5个v）：
vvvvv
首先先考虑只变两个v的情况：
- wvvv
- vwvv
- vvwv
- vvvw
接着是变化四个v：
- wwv
- wvw
- vww
这样一算，共有7种可能。
更一般地，推广到长度为n的“v序列”，我们枚举以下可能：
- 变化两个v：
- wvvv...(n-2个v)
- vwvv...
- vvwv...
- ...w可以一次占有n-1个位置，一共有n-1种。
- 变化四个v：
- wwv...(n-4个v)
- wvw...
- ...一共有n-2种。
- ...
- 变化[n/2]个v（
[]是取整符号，因为要考虑到当n是奇数，最后一个v不够变化两个）：- www...w(v)
- 一共有1种。
所以，显而易见，最终的情况就是(1+2+...+n-1)。
代码时注意
- 根据上面的解析，我们容易知道要使用斐波那契数列。此时请您预处理好fib数列。
- 请注意取模$10^9+7$。应当在fib数列预处理中就要进行。
AC Code
``` #include <bits/stdc++.h> using namespace std; string s; long long ans=1; long long fib[100005]; long long mod=1e9+7; long long solve(long long num){ return fib[num+1]%mod; } int main(){ //init fib fib[0]=0; fib[1]=1; for(int i=2;i<=100000;i++){ fib[i]=(fib[i-1]%mod+fib[i-2]%mod)%mod; } cin>>s; if(s.find("m")!=-1||s.find("w")!=-1){ cout<<0; return 0; } for(int i=0;s[i];i++){ if(s[i]=='u'){ long long now=i; while(s[i]&&s[i]=='u'){ i++; } ans*=solve(i-now)%mod; ans%=mod; i--; } if(s[i]=='n'){ long long now=i; while(s[i]&&s[i]=='n'){ i++; } ans*=solve(i-now)%mod; ans%=mod; i--; } } cout<<ans%mod; return 0; } ```CF180C Letter
题意
给你一个字符串，我们每一次操作都可以将一个大写字母变成任意小写字母，当然同理也可以将小写字母变成任意大写字母，问最少操作多少次，能够使得字符串变成前边都是大写字母，后边都是小写字母。