暑期强化DP学习的一个计划，每天刷点cf，每日赛过活神仙（bushi）

1.CF_1660C（1300）

点此处直达

tag -> greddy dp string

题目大意：

现在给定一个概念：偶数字符串：只要满足字符串长度为偶数并且每一个奇数i满足a[i]==a[i+1]。

题目要求对于一个字符串，最少删除多少个字符可以得到一个偶数字符串，删除的位置任意，不一定连续，不改变原来相对位置。

思路：

直接for循环遍历，如果遍历到i，发现a[i]已经存在且上次存在的位置为j，那么子串[j,i]就可以贡献出长度为2的偶数字符串，利用补集思想，求出可以得到的最长的偶数字符串，用原长度-最长偶数字符串长度即可得到答案。

贪心策略证明：

对于一段字符串aoeoaee，刚开始枚举时aoe均未出现过，不可以贡献结果，当第一次出现第二个o的时候，发现oeo可以把e给去掉组成一个偶数字符串，此时得到ooaee，（因为前面的a肯定也没有办法再组成偶数字符串了，题目要求从任意位置删除字符，并不可以改变原来字符的相对位置），再往后遍历a只出现了一次，e出现了一次，当e出现第二次的时候又贡献出ee的一个偶数字符串，此时只出现一次的a也无法再与别的组成偶数字符串，因此最终可以构建出ooee的偶数字符串，那么需要去除的长度为7-4=3

对于字符串aoeoaee也可以构建出来aaee的偶数字符串，但是我们最终并不是求有多少种偶数字符串的构建方法，只是求一个满足条件的最长的偶数字符串长度，因此该贪心策略满足。

2.CF_1631B（1100）

点击此处直达
tag -> greedy dp

题目大意：

给定一个长度为 $n$ 的数据 $a$。你可以执行若干次操作，每次操作你可以选择一个位置 $i$ 和一个整数 $k$，但需要保证 $1⩽l⩽l+2\cdot k-1⩽n$，$k⩾1$。然后对于所有的 $0⩽j⩽k-1$，将 $a_{i+j}$ 的值替换为 $a_{i+k+j}$。你希望最终得到一个所有元素的值相等的数组，求最小的操作次数。

思路：

由题目我们可以得到一个性质：最终的序列一定为全部由a[n]组成的序列，所以我们只需要从后往前遍历，一旦发现一个不等于a[n]的数，然后用后面最长的连续的a[n]序列去覆盖，然后统计即可。

初做题的误区，利用双指针+倍增，每次覆盖2^k长度的区间进行统计，然而并不是最优。

比如1 1 1 4 4 4 4 4 1 4 1 4 1 4

如果按照2^k倍增，应该是

1 1 1 4 4 4 4 4 1 4 1 4 4 4

1 1 1 4 4 4 4 4 1 4 4 4 4 4

1 1 1 4 4 4 4 4 4 4 4 4 4 4

4 4 4 4 4 4 4 4 4 4 4 4 4 4

一共四步

然而正解应该是

1 1 1 4 4 4 4 4 1 4 1 4 4 4

1 1 1 4 4 4 4 4 4 4 4 4 4 4

4 4 4 4 4 4 4 4 4 4 4 4 4 4

一共三步

3.CF_1703G

点击此处直达
tag -> dp , greedy , brute force , bitmasks

题目大意：

有 n 个箱子需要按顺序打开，第 i 个箱子中有 ai个金币，可以用好钥匙和坏钥匙去开箱子，好钥匙需要花费 k 个金币，坏钥匙不花费金币，但是会使当前这个箱子开始到第 n 个箱子中的金币全部减半。开箱的过程中金币可以是负数的，即可以赊账，问最多能留下多少硬币。

思路：

看到此题的时候，老贪心侠的毛病又犯了，直接想了一个贪心策略：如果好钥匙开可以赚钱那就用好钥匙开，不然就用坏钥匙开。

然而显然肯定是不可以的，因为可能用坏钥匙开造成的利益损失可能远大于好钥匙开的短暂的小的损失，比如如果好钥匙开箱子的钱是5块，现在又6 4 18 20四个箱子，按照贪心策略，应该是：

6-5 4/2 18/2-5 20/1-5 加起来是12

然而如果全部用好钥匙开，那么就是

6-5 4-5 19-5 20-5 加起来是28远大于12，所以贪心策略失败，不可以仅仅考虑当前局部的最优化利益

贪心不行就得往dp方面去思考了，我们对于每一个物品都有两个选择，要么用好钥匙开，要么用坏钥匙开，那么我们完全可以把所有的情况枚举出来，进行判断。然而O(2ⁿ)的时间复杂度过于可怕，所以我们使用dp递推式，我们知道a[i]最大是2³²所以最多需要考虑使用33次坏钥匙的情况，因为33次坏钥匙之后，你再怎么使用坏钥匙，那对最终的结果都不会产生任何影响了，因为任何一个数经够32次/2都会变成0，对答案没有正向贡献。

方程概念:定义f[i][j]表示前i个巷子用了j个坏钥匙开所得到的最大的收益。

决策：

对于第i个物品，有两个决策，分别是用好钥匙开，和用坏钥匙开

状态转移：

如果第i个物品用好钥匙开，那么就从前i-1个物品用j个坏钥匙开转移过来；

如果第i个物品用坏钥匙开，那么就从前i-1个物品用j-1个坏钥匙开转移过来；

所以状态转移方程式为：f[i][j]=max(f[i-1][j]+(a[i]>>j)+k,f[i-1][j-1]+(a[i]>>j))

本题相当于一个背包变形的一个01决策问题，解题的关键在于看出33次是坏钥匙的最大限制，后面对结果都没有正向贡献所以不予以考虑。
参考代码：

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 7;
ll a[MAXN];
ll f[MAXN][35];
void init(int n)
{
    
    for(int i=0;i<=n+1;i++)
    {
    
        for(int j=0;j<=34;j++)
        {
    
            f[i][j]=-1e18;
        }
    }
    for(int i=0;i<=n+1;i++)
        a[i]=0;
}
int main()
{
    
    int t;
    cin>>t;
    while(t--)
    {
    
        int n,k;
        cin>>n>>k;
        init(n);
        for(int i=1;i<=n;i++)
            cin>>a[i];
        f[0][0]=0;
        for(int i=1;i<=n;i++)
        {
    
            for(int j=0;j<=33&&j<=i;j++)
            {
    
                f[i][j]=max(f[i][j],f[i-1][j]+(ll)((a[i]>>j)-k));//第i个用好钥匙开
                if(j!=0)
                    f[i][j]=max(f[i][j],f[i-1][j-1]+(ll)((a[i]>>j)));//第i个用坏钥匙开的
            }
            f[i][33]=max(f[i][33],f[i-1][33]);//不能忘了把所有坏钥匙全用了的情况
        }
        ll res=-1e18;
        for(int i=0;i<=33;i++)
            res=max(res,f[n][i]);
        cout<<res<<endl;
    }
}

4.CF_1618D（1300）

点此处直达
tag -> greedy , dp

备注：纯纯的一个贪心思维题

题目大意：

给定 $n$ 个数和一个数 $k$，要求对这 $n$ 个数进行 $k$ 次操作，每次操作取出两个数 $a_i,a_j(i\ne j)$，并将 $\lfloor \frac{a_i}{a_j}\rfloor$ 加进得分中，其中 $\lfloor \frac{x}{y}\rfloor$ 为不超过 $\frac{x}{y}$ 的最大整数。$k$ 次操作后，将剩下的 $n-2k$ 个数直接加入到得分中。求最终得分的最小值。

思路：

我们任选两个数得到的最小增益要么是0要么是1（相同为0，相同为1）

题目要求最终剩下的数字和也要尽可能小，所以首先需要排序预处理，所以我们任务很明确就是对于序列中后2k的元素进行选取，使得每次选取的两个元素尽可能不一样，由于我们的序列是排序过的，如果按照相邻选取则可以达到尽可能多选一样的元素的效果，我们要求不一样，所以可以间隔着选取，若一共选2k个元素，那么第一个就和第k+1个作为1组，第2个就和第k+2个作为1组，贪心策略成立。

5.CF_1633D（1600）

点击此处直达
tag ->dp , greedy

备注：01背包变形，思路还挺好想的

题目大意：

你有一个长度为 $n$，初始全为 $1$ 的数组 $a$，和两个长度为 $n$ 的数组 $b,c$。
你可以最多进行 $k$ 次如下的操作：选择两个正整数$i,x$，使 $a_i$ 变成 $\left(a_i+\lfloor \frac{a_i}{x}\rfloor \right)$。

最后，如果 $a_i=b_i$，你将会获得 $c_i$ 的收益。

最大化总收益。

思路：

常规想法：由于最多可以进行k次增值操作，每一个物品增值到所需要的数值所需要的操作数是不一样的，所以我们要尽可能地用最少地操作数去获得最多的价值，显然用dp，那么对于每一个物品都有取和不取两个决策，如果这个物品取，则在当前状态需要消耗t[b[i]]次操作数，如果不取则不需要消耗操作数。

本题题目很清楚，给定了最多操作的次数，并且是求有限次数操作下的最大收益，我们如果把操作次数当作物品的重量，本题就自然而然变成了01背包问题。

变量定义：f[j]：消耗j个操作数得到的最大收益

最终所求f[0…k]的最大值

状态转移：01背包的方程（f[j]=max(f[j],f[j-t[b[i]]+c[i])）

本题需要一个初始化操作，即求t[0…1000]，暴力即可，时间复杂度10⁶.

参考代码：

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int MAXN = 1e3+ 7;
const int MAXM=1e6+7;
int b[MAXN],c[MAXN],f[MAXM],t[MAXM];
void init(){
    
	for(int i = 1 ; i <= 2000 ; i++)
		t[i] = 1e9;
	t[1] = 0;
	for(int i = 1 ; i <= 2000 ; i++)
		for(int j = 1 ; j <= i ; j++)
			t[i + i / j] = min(t[i + i / j], t[i] + 1);
}
int main()
{
    
    init();
    int T;
    cin>>T;
    while(T--)
    {
    
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>b[i];
        for(int i=1;i<=n;i++)
            cin>>c[i];
        memset(f,0,sizeof(f));
        f[0]=0;
        for(int i=1;i<=n;i++)
        {
    
            for(int j=k;j>=t[b[i]];j--)
            {
    
                    f[j]=max(f[j],f[j-t[b[i]]]+c[i]);
            }
        }
        int res=0;
        for(int i=0;i<=k;i++)
            res=max(res,f[i]);
        cout<<res<<endl;
    }
}

6.CF_1644C（1400）

点击此处直达
tag -> brute force , greedy , dp

备注：一个很好的线性思维dp题

题目大意：

给定一个序列 $\left\{a_n\right\}$ 与 整数 $x$

定义 $f(k)$ 表示经过如下操作后, 序列 $a$ 中最大的连续子段和: 将 $a$ 中 $k$ 个不同的位置上的数加上 $x$

请求出 $f(k),k\in [0,n]$

思路：

对于本题，要求操作之后的最大连续子段和，我们首先能想到的一个贪心策略是，对于想要使k个元素分别加x，并且让最后的最大连续子段和最大，那么肯定把这k个元素加在原本身的长度大于等于k的最大连续子段和上，这样才会让最后结果货真价实地增加k*x，所以我们首先需要利用dp求出来长度为[0…n]的最大子段和分别为多少，然后再在其基础上加上k*x即可

本题出现了单一变量复用的情况。

一开始f[i]表示长度为i的最大连续子段和

到后面f[i]转义表示长度大于等于i的最大连续子段和

参考代码：

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 7;
int a[MAXN],f[MAXN],dp[MAXN];
//dp[i]表示增加长度为i的最大连续字段和时候所获得的总和
int main()
{
    
    int t;
    cin>>t;
    while(t--)
    {
    
        int n,x;
        cin>>n>>x;
        memset(a,0,sizeof(a));
        memset(f,0,sizeof(f));
        memset(dp,-0x3f,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
    
            cin>>a[i];
            f[i]=f[i-1]+a[i];
        }
        for(int i=1;i<=n;i++)
        {
    
            for(int j=i;j<=n;j++)
            {
    
                dp[j-i+1]=max(dp[j-i+1],f[j]-f[i-1]);//状态转移求长度为j-i+1的最大连续字段和
            }
        }
        dp[0]=max(dp[0],0);
        for(int i=n-1;i>=0;i--)
            dp[i]=max(dp[i],dp[i+1]);//f[i]改变含义，转为求长度大于等于i的最大连续子段和
        for(int k=1;k<=n;k++)
            dp[k]=max(dp[k-1],dp[k]+k*x);//统计最后答案
        for(int i=0;i<=n;i++)
            cout<<dp[i]<<" ";
        cout<<endl;
    }
}

7.CF_1553C（1200）

点击此处直达
tag -> bitmasks , brute force , dp , greedy

标签：贪心思维题，动脑子

题目大意：

现在一共有 $10$ 次罚球机会，其中奇数次属于队伍 $1$，偶数次属于队伍 $2$。

在罚球开始前，你预先知道了每一次罚球是必定成功（字符 $1$），必定不成功（字符 $0$），还是由你操纵（字符 $?$）。当一次罚球成功时，所在的队伍就会得到 $1$ 分，最终得分高的队伍获胜。

当裁判发现某个队伍必胜的时候，就会宣布停止罚球（注意，裁判并不能预知罚球结果）。现在，你希望罚球的轮数尽可能少，求出这个轮数。

思路：

什么时候可以确定后面不需要比了？

当前某一个队伍已经获得的分数+剩下还没获得的最大可以获得的分数＜另一个队伍已经获得的分数

所以我们只需要利用贪心策略：压倒性支持某一个队伍，只要是？而且是我们支持的队伍，那就一定让他赢，只要是？但是不是我们支持的队伍，那就一定让他输！

当然我们采用墙根草战术，两个都支持一下，看看两个队伍的表现怎么样，支持谁结束比赛的轮数更少那就支持谁。

核心代码：

while(t--){
    
	cin>>s;
	cout<<min(cal1(),cal2())<<endl;
}
//cal1()是全力支持第一个队伍最快能结束的时间
//cal2()是全力支持第二个队伍最快能结束的时间