#include <cstdio> #include <iostream> using namespace std; const int N = 1e5 + 10; typedef long long LL ; LL a[N]; LL d[N]; int n, m; int main() { scanf("%d%d", &n, &m); int tmp; for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); ...

cnt['c']记录字符'c'出现的次数 dp['c']记录以字符'c'结尾的长度为2的子序列的个数，就是"*c"这种形式，两个字符是不一样的，就是叠词的前两个字符。 遍历s中的每个字符，假设i=k时，遇到字符x，res = res + dp[x]，就是s[0~k-1]中的答案数加上遍历到字符结尾的长度为2的子序列的个数(之前长度为2，现在遇到了x，就满足叠词要求，dp[x]就是由于遍历到了x字符，新出现的叠词数) 那遇到新的x，记录字符'c'结尾的长度为2的子序列的个数也要更新：dp[x] = 之前的数量+遍历到的这个x所能形成的个数=dp[x] + (i-cnt[x]...

求二维前缀和矩阵 公式：mat[i][j] = mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1] + 求解给定矩形范围的数字和 公式：ans(x1,y1,x2,y2) = mat[x2][y2]-mat[x2][y1-1]-mat[x1-1][y2]+mat[x1-1][y1-1] #include <cstdio> #include <iostream> using namespace std; const int N = 1010; typedef long long LL ; int n,m,q; LL mat[N][N]; int ...

很简单，求数组前缀和数组，ans = pres[r]-pres[l-1]，下标从1开始，很方便。 #include <cstdio> #include <iostream> using namespace std; const int N = 1e5+10; typedef long long LL; int n,q; LL pres[N]; int main() { scanf("%d%d", &n,&q); LL tmp = 0; int a; for(int i = 1; i <= n; i...

和买卖股票的最好时机(三)思路类似： dp[n][k*2]中的dp[i][kk]： 当kk==0、2、4、6...，是第1、2、3、4...次持有状态 当kk==1、3、5、7...，是第1、2、3、4...次不持有状态 初始化： 所有的第一天的 任何次 持有状态的收益值都是 -p[i]，所有的第一天的 任何次 未持有状态的收益值都是 -p[i] #include <cstdio> #include <iostream> using namespace std; const int N = 1010; int p[N]; int n, k; int dp[N][210]...

只能交易两次，还是从状态出发 dp[i][0]：第i天第一次持有 dp[i][1]: 第i天第一次未持有/卖出 dp[i][2]：第i天第二次持有 dp[i][3]：第i天第二次未持有/卖出 状态转移： dp[i][0] = max(dp[i-1][0]"维持状态，和前一天一样处于第一次持有状态，收益不变", -p[i]"第一次买入，总收益为-p[i]，花掉了当前价格的钱") dp[i][1] = max(dp[i-1][1]"维持状态，未持有，没买过",dp[i-1][0]+p[i]"前一天还持有，今天卖了，收益就是加上今...

动态规划 dp[N][2]: dp[i][0]表示第i天不持有股票的最大收益，同理，dp[i][1] 表示第i天持有股票的最大收益。 分析： dp[i][0]，第i天不持有股票（卖出股票），那这个状态可以来自两方面：1）来自dp[i-1][0]，前一天不持有股票，今天也不持有股票，最大收益不会变化；2）来自dp[i-1][1]+p[i]，前一天持有股票，今天不持了（卖了），买股票的时候是负收益，花钱了，所以现在卖了股票是加上今天的价格p[i]。综上，有 dp[i][0] = max(dp[i-1][0], dp[i-1][1]+p[i])。 dp[i][1]，第i天持有股票，本身包含两种状态：...

用lastMin记录遍历到的i之前的出现的最小值1.当 p[i]<=lastMin，说明p[1~i]上的最大收益和p[1~i-1]上一样， f[i] = f[i-1]2.当p[i]>lastMin，说明有可能产生更大的收益，f[i] = max(f[i-1], p[i]-lastMin) #include <cstdio> #include <iostream> using namespace std; const int N = 1e5+10; int n; int prices[N]; int dp[N]; //dp[i]表示 prices[1:i]上...

如果不考虑L的范围，就是一道简单的dp题。f[i]表示走到位置i，踩到的石头个数的最小值，则f[i]=min(f[i], f[j] + flag[i])，其中flag[i]表示位置i是否是石子，j在[i-s, i-t]之间。当L很大时，但是石子个数很少最多只有100个，所以存在两个石子之间有很大的空隙。下面分两种情况来讨论：当s==t：走法唯一，每次跳的距离为s，统计在位置满足是s的整数倍的上的石子的个数当s!=t： 我们考虑不能被s, s+1, s+2, ..., T 所表示的数有哪些。结论：如果我们只用两个相邻的数p， q，那么不能被表示的数的最大值是(p-1)(q-1)-1，因此所有大于...

「贪心」地进行正向查找，每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数。 #include <cstdio> #include <iostream> using namespace std; const int N = 1e5 + 10; int nums[N]; int n; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &nums[i]); } ...

如果最大分数存在，最后一个数一定在里面初始化pos为n-1，不断向前遍历，看遍历到的位置i能否跳到pos，能说明从 i 最终可以跳到最后。如果i遍历过了0，而pos还未更新到0，说明数组不能跳到最后。举个例子：[1,2,3,0,0,1,4]，n=7。初始pos = 6 -> i=5，nums[5]=1可以跳到pos位置，更新位置pos=5，1加入分数中 -> i=4，不能动 -> i=3，不能动 -> i=2，nums[2]=3可以跳到pos=5，更新位置pos=2，3加入分数中 -> i=1, nums[1]=2可以跳到pos=2，更新pos=1，2加入分数中 ...

记录最远可以到达的地方，在遍历每个nums时，更新最远的距离 #include <iostream> using namespace std; const int N = 2e5+10; int a[N]; int n; int main() { scanf("%d",&n); for(int i = 0; i < n; i++){ scanf("%d", &a[i]); } //最远位置 int farthest = 0; bool ans = true;...

选中a_i，删除数组中每一个a_i+1和a_i-1的数。可以遍历1到10000中的每一个数字，出现在给定的数组中就统计次数，因为最后也是需要输出得分的。这样就是对数组counts进行动态规划转移方程数i 不选，它可以来自自身减一的数的两种状态的最大值dp[i][0] = max(dp[i-1][0], dp[i-1][1])数i 选，它只能来自自身减一的数在不选择的状态下，加上自身的分数（值*数量）dp[i][1] = dp[i-1][0] + i * counts[i] #include <iostream> using namespace std; int counts[100...

环形的家不能同时偷第一个和最后一个。这里家的编号是从1到n。1 不偷第一个家：遍历到第i个家时，有两种情况，偷或者不偷，取二者的最大值。i的遍历范围：[3,n]，给定初值: dp1[1]=0, dp[2] = a[2]dp1[i] = max(dp[i-2]+a[i], dp[i-1])2 偷第一个家：遍历到第i个家时，有两种情况，偷或者不偷，取二者的最大值。i的遍历范围：[2,n-1]，给定初值: dp1[0]=0, dp[1] = a[1]dp1[i] = max(dp[i-2]+a[i], dp[i-1])这样可以用同一个转移方程 #include <iostream> us...