Shaass拥有n本书。他想为他的所有书制作一个书架，并想让书架的长宽尽量小。第i本书的厚度是t[i]，且这本书的纸张宽度是w[i]。书的厚度是1或2，所有书都有同样的高度（即书架的高是均匀的）。 Shaass以以下的方式摆放这些书籍。 1.他选择了一些书并竖直摆放它们。 2.他将剩余的书籍水平纺织于竖直的书上面。 水平放置的书的宽度和不能多于竖直放置的书的总厚度。图中描绘了书籍的样本排列。 帮助Shaass找到可以达到的书架长度最小值。 背包问题的变形，我们可以将一本书长度与厚度的和类比为体积，厚度类比为价值，设所有书全部竖直放置时书架的长度为总体积，我们就可以求出水平放置的书可以提供的最大...

找到一串序列a中的一段最长子序列，子序列满足x,y,x,y,x,y...交替的形式。 dp[i][j] 表示以a[i]为开始a[j]为结尾的最长交替子序列 dp[i][j] = dp[j][k] + 1 (a[i] == a[k] 形成交替) #include <bits/stdc++.h> using namespace std; const int maxn = 4005; int dp[maxn][maxn]; int a[maxn]; int main() { int n; cin >> n; for (int i = 1; i<= n; i++) cin...

给你一个小写字符串str和26个整数a[i]，是用来限制（字母i所在的字符串不能超过a[i]） 输出分割字符串的方案数。输出所有方案中，最少的分割次数。输出所有方案中，最大的子串长度。 dp[i][0] 表示前i个字母正确分割的数量dp[i][1] 表示前i个字母正确分割且数量最少dp[i][1] 表示前i个字母正确分割且最大子串的长度最大 dp[i][0] = dp[i][1] + dp[j - 1][0]dp[i][1] = min(dp[i][1], dp[j - 1] + 1)dp[i][2] = max(dp[i][2], max(i - j + 1, dp[j - 1][2])) ...

题意：给定一个数组{an}，问这个数组的所有子序列{bm}中，有多少子序列满足:对于所有的i(1<=i<=m)满足bi是i的倍数，答案对10^9+7取模 题解： 首先想到二维DP，从i长中找到j长的子序列的方法=dp[i][j] 如果a[i]可以除以j，原式=dp[i-1][j-1]+dp[i-1][j] 否则，原式=dp[i-1][j]； j可以通过枚举a[i]的因数得到 然后我们发现可以把i这个维度压掉… #include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; const int ...

Given is a string SS. Each character in SS is either a digit (0, ..., 9) or ?. Among the integers obtained by replacing each occurrence of ? with a digit, how many have a remainder of 55 when divided by 1313? An integer may begin with 00. Since the answer can be enormous, print the count modulo 109+...

题目描述： 有n个人(1<=n<=1000)。每个人有一个重量wi(1<=wi<=1000)和一个魅力值bi(1<=bi<=10^6)。 n个人之间有m(1<=m<=min(n*(n-1)/2, 10^5))个关系。第i个关系由两个数字xi和yi组成，表示第xi个人和第yi个人是朋友，朋友关系是双向的。 已知若a和b是朋友，b和c是朋友，则a和c是朋友。 现在Mehrdad要邀请一些人来到派对，使这些人的重量总和不超过wi(1<=wi<=1000)，且魅力值总和尽量大。同一个朋友圈里的人，只能邀请其中的一个人，或者全部人，或者一个人也...

给定一个2×n的棋盘，可以对上面的格子黑白染色，求染色后棋盘上的联通块的个数正好为k的染色方案数。用0：表示001：表示112：表示103：表示01dp[i][j][k] 表示第i个位置用j状态是有k个联通块的数量然后枚举当前位置的状态与前一个的状态形成的联通块的数量 #include <bits/stdc++.h> using namespace std; const int maxn = 2005; const int mod = 998244353; int dp[maxn][4][maxn]; /* 0:00 1:11 2:10 3:01 */ // 1:01 02, 03...

给出 个整数 ， 个查询，对于一个查询 ，对应于子段 ，需要你判断这个子段是不是单峰的。  b1 ≤ b2 ≤ ... ≤ bx ≥ bx + 1 ≥ bx + 2... ≥ bk 此处的单峰，指的是，开始时是一段单调不减的，然后以一段单调不增结束；同时这两段的长度为零也是可以的。 L[i] 表示i位置向前能走多远R[i] 表示i位置向后能走多远如果 R[r] + L[l] >= r - l + 1 表示是单存在当峰 #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; int a[ma...

题意:有n棵树,m种颜色，让你分成k段，数字0代表该树没没有进行染色，需要你从m种颜色中选择一个为其染色，染色的过程中需要消耗代价，求最小代价(已有颜色不必再染色)  dp[i][j][k] 表第i个位置颜色为j分为k分的最小代价 然后分类讨论：情况1：col[i]和col[i - 1]都存在情况2: col[i]存在，col[i - 1]不存在情况3: col[i]不存在，col[i - 1]不存在情况4：col[i]和col[i - 1]都不存在 #include <bits/stdc++.h> using namespace std; const int maxn = 105...

#include <bits/stdc++.h> using namespace std; const int maxn = 5e6 + 5; const int maxm = 5e6; int prime[maxn], cnt; bool isprime[maxn]; int sum[maxn]; void getPrime(int n) { isprime[1] = 1; for (int i = 2; i <= n; i++) { if (!isprime[i]) { prime[++cnt] = i; sum[i] = 1; } for (int j = 1; j &...

给定一个长度为n的序列，选出k组不重叠且连续的m个数，使其和最大 1<=m*k<=n<=5000（有负数） dp[i][j] 表示前i个数分为j分的最大值转移方程为：dp[i][j] = dp[i - 1][j] + dp[i - m][j - 1] + sum[i] - sum[i - m];dp[i - 1][j] 表示不选择该数dp[i - m][j - 1] + sum[i] - sum[i - m] 表示选择该数 #include <bits/stdc++.h> using namespace std; const int maxn = 5005; ty...

问最多修改一个数字，序列可获得地最大严格递增字段长度为多大；维护一个L[i] 数组L[i] 表示第一个a[i] <= a[i - 1] 的位置L[1] = 1; 对于每个位置i  #include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 5; const int inf = 1e9; int a[maxn]; int L[maxn]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++)...

题意:有两种花可以吃，white花只能连续吃k个，red花不受限制，当吃a到b朵花时一共有多少种吃法？注意：(WWWR)不算，因为W(W没有k)个连续 WWR 所以：dp[i]表前i个合法的数量则: dp[i] = dp[i - 1] + dp[i - k]dp[i - 1] 相当于当前位置为R(没有限制)dp[i - k] 相当于当前位置为W(i-k这个范围为W) #include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; const int maxn = 1e6 + 5; const int ma...

题意：面包师Lavrenty打算用馅料做几个面包，然后把它们卖掉。Lavrenty有n克面团和m种不同的馅料。馅料种类的下标从1到m，他知道他的第i种馅料剩下ai 克，做一个第i种馅料的面包，恰恰需要bi克的i种馅料 和 ci 克的面团，同时这种面包可以卖di 块Tugrik。他也可以做没有馅的面包。每个这样的面包需要c0克面团，可以卖d0块Tugrik。所以Lavrenty可以做任何数量的包子，用不同的馅料或者不用馅料，除非用完了面团和馅料。Lavrenty会扔掉烘培面包后剩下的所有多余材料。求出Lavrenty可以赚取的Tugrik的最大数量。 思路：将问题转换为多重背包问题，将每种馅料打...