A-尺取法/双指针

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

#include<iostream>
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<s.size();i++)    //固定右端点
    {
        if(s[i]=='R') cnt++;
        
        while(cnt==k&&j<=i)     //当区间符合条件时，移动左端点计算方案数
            cnt-=(s[j++]=='R');
        
        ans+=j;
    }
}

int main()
{
    string s;
    cin>>n>>k>>s;
    
    string t="";
    for(int i=0;i<n;i++)    //字符‘P’将字符串分割成多个子字符串
    {
        if(s[i]=='P') sum(t),t="";
            else t+=s[i];
    }
    
    sum(t);    //别忘了最后还剩下一段没计算！
    
    cout<<ans<<endl;
    return 0;
}

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]由哪些状态推导来）

1. 不选第 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]
2. 选第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个物品影响了什么)

1. 不选: d p [ i ] [ j ] — — > d p [ i − 1 ] [ j ] dp[i][j]——>dp[i-1][j] dp[i][j]——>dp[i−1][j]
2. 选： 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<iostream>
#include<cstring>
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<k;j++)
            dp[i][j]=-1e16;
    dp[0][0]=0;
    
    for(int i=1;i<=n;i++)
        for(int j=0;j<=k;j++)
        {
            dp[i][j]=max(dp[i][j],dp[i-1][j]);    //不取
            dp[i][(j+a[i])%k]=max(dp[i][(j+a[i])%k],dp[i-1][j]+b[i]);    //取
//             dp[i][j]=max(dp[i][j],dp[i-1][(j-a[i]%k+k)%k]+b[i]);    //取
        }

    if(dp[n][0]<=0) puts("-1");
    else cout<<dp[n][0]<<endl;
    
    return 0;
}