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

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

#include
using 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 
I - DP/01背包变形 
传统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
#include
using 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