2022牛客寒假算法基础集训营4

时间：2023-05-31

A-尺取法/双指针字符串按 ′ P ′ 'P' ′P′分割成了多个子字符串，我们求出子字符串满足 c n t ≥ k cnt≥k cnt≥k的子串数量则为答案。对于不含 p p p的子串，固定右端点，左端点具有单调性，右端点 i i i每次向右移动，左端点 j j j也向右移动。

#includeusing namespace std;const int N=2e5+100;int n,k;long long ans=0;void sum(string s) //求字符串s至少包含k个R的子串有多少个{ int cnt=0,j=0; for(int i=0;i>n>>k>>s; string t=""; for(int i=0;i 传统01背包的模型是，每个物品有一个重量和一个价值，问总重量不超过 x x x能取到的最大价值
而这道题的模型变成了：总重量必须是 x x x的倍数时能取到的最大价值。
解法其实是一样的，不同的是本来要维护前 i i i 个物品重量为 j j j的最大值，现在变成了前 i i i个物品重量模 k k k为 j j j的最大值

d p [ i ] [ j ] dp[i][j] dp[i][j]表示：考虑前j个物品，消耗总和% k = j k=j k=j的威力最大值
因为求的是最大值，区分于求方案数的DP，dp方程不再累加，而是求max

集合划分：
考虑1：
（ d p [ i ] [ j ] dp[i][j] dp[i][j]由哪些状态推导来）
不选第 i i i个物品， d p [ i ] [ j ] — — > d p [ i − 1 ] [ j ] dp[i][j]——>dp[i-1][j] dp[i][j]——>dp[i−1][j]选第i个物品， d p [ i ] [ j ] — — > d p [ i − 1 ] [ ( j − a [ i ] ) ] dp[i][j]——>dp[i-1][(j-a[i])] dp[i][j]——>dp[i−1][(j−a[i])]% k + b [ i ] k+b[i] k+b[i]
(这样考虑的话，涉及负数取模)
负数取模的技巧：先转化为绝对值小于k的负数，然后再加k再模k
d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i − 1 ] [ ( j − a [ i ] dp[i][j]=max(dp[i][j],dp[i-1][(j-a[i] dp[i][j]=max(dp[i][j],dp[i−1][(j−a[i]% k + k ) k+k) k+k)% k ] + b [ i ] ) k]+b[i]) k]+b[i])
考虑2:
(是否选定第i个物品影响了什么)
不选: d p [ i ] [ j ] — — > d p [ i − 1 ] [ j ] dp[i][j]——>dp[i-1][j] dp[i][j]——>dp[i−1][j]选： d p [ i ] [ ( j + a [ i ] ) dp[i][(j+a[i]) dp[i][(j+a[i])% k ] — — > d p [ i − 1 ] [ j ] + b [ i ] k]——>dp[i-1][j]+b[i] k]——>dp[i−1][j]+b[i]
d p [ i ] [ ( j + a [ i ] ) dp[i][(j+a[i]) dp[i][(j+a[i])% k ] = m a x ( d p [ i ] [ ( j + a [ i ] ) k]=max(dp[i][(j+a[i]) k]=max(dp[i][(j+a[i])% k ] , d p [ i − 1 ] [ j ] + b [ i ] ) k],dp[i-1][j]+b[i]) k],dp[i−1][j]+b[i])
#include#includeusing namespace std;const int N=1100;long long dp[N][N],n,k;long long a[N],b[N];int main(){ cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; //求最大值前初始化 for(int i=0;i<=n;i++) for(int j=0;j

上一篇：第一篇博文——与君共勉

下一篇：C++STL详解list的介绍及其使用

相关推荐

MySQL数据库的安装与账户注册登陆说明