#include<bits/stdc++.h> using namespace std; int main() { string str; //存放输入的字符串 while(getline(cin, str)) { //获取输入的一行字符串 vector<string> digitalstr; //容器digitalstr用来存放最长的数字子串 int length = str.length(); //length为输入字符串的长度 int maxlen = 0; //maxlen记录最长数字子串的长度 for(int i=0;i<length;i++) { //...

#include<iostream> #include<vector> using namespace std; int main(){ int M,N; cin>>M>>N;// 由于价格是10的整数倍，处理一下以降低空间/时间复杂度 M/=10; vector<vector<int>> price(N+1,vector<int>(3,0));// 价格 vector<vector<int>> value(N+1,vector<int>(3,0));// 重要程度 for(...

#include <bits/stdc++.h> using namespace std; int lengthOfLIS(vector<int>& nums) { vector<int> dp(nums.size()+1,0); for(int i=1;i<nums.size();i++){ for(int j=0;j<i;j++){ if(nums[i]>nums[j]) dp[i]=max(dp[j]+1,dp[i]); } } int result=0; for(int i=0;i<nums.size();i++){ ...

#include <bits/stdc++.h> using namespace std; int main(){ int m, n; while(cin >> m >> n){ vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); //dp[i][j]表示i个苹果放在j个盘子的分法 for(int i = 1; i <= n; i++) dp[0][i] = 1; //0个苹果只有1种分法 for(int i = 1; i <= m; i++) for(i...

#include<bits/stdc++.h> using namespace std; int main(){ int n; while(cin >> n){ // 输入的数组 int tmp; vector<int> v; for (int i = 0; i < n; ++i){ cin >>tmp; v.push_back(tmp); } // 最长递增子序列 if (v.empty()) return 0; vector<int> dp1(n, 0); for (int i = 0; i < n; ++i){ dp...

#include <bits/stdc++.h> using namespace std; int minDistance(string word1,string word2){ vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0)); for(int i=0;i<=word1.size();i++) dp[i][0]=i; for(int j=0;j<=word2.size();j++) dp[0][j]=j; for(int i=1;i<=wo...

/*怎么去重，用set集合。 秤砝码问题中的集合法是一种利用集合数据结构来解决多重背包可达性问题的高效方法。该方法的核心思想是维护一个集合，记录当前所有可能达到的重量值。 集合法的实现步骤 1.初始：创建一个空集合，用于存储所有可达的重量值。初始时，将重量0加入集合，表示不使用任何砝码的情况。 2.处理每种砝码‌：对于每一种砝码（重量为 w，数量为 c），执行以下操作： 创建一个新的集合，用于存储当前处理完该砝码后所有可能的重量值。 遍历当前集合中的每一个可达重量Wold。 对于k从1到c，计算Wnew=Wold+k×w。 将所有计算出的Wnew加入新集合中。 3.更新集合:将新集合替换旧集合...

//画个二位数组图，显然可以得出，若当前匹配字符相同，则最长公共子串等于左上角对角线长度+1. #include <bits/stdc++.h> using namespace std; int longestCommonSubsequence(string text1, string text2) { vector<vector<int>> dp(text1.length()+1,vector<int>(text2.length()+1,0)); int result=0; for(int i=1;i<=text1.length();i+...

#include <bits/stdc++.h> using namespace std; int main() { string s; cin>>s; int n = s.length(); if (n == 0) return 0; int minChanges = INT_MAX; // 前半部分和后半部分 string left = s.substr(0, n/2); string right = s.substr(n/2); // 统计前半部分字符频次 vector<int> leftCount(110000, 0); for (char c : ...

#include<iostream> #include<string> #include<algorithm> #include<vector> using namespace std; int main(){ string s; while(cin >> s){ int n = s.length(); vector<vector<bool> > dp(n, vector<bool>(n, false)); //dp[j][i]=1表示从j到i是回文子串 int maxlen = 1; //初始为1...

//和最长回文子串是同一道题 #include <iostream> #include <string> using namespace std; int main() { string s; cin >> s; int n = s.size(); int m = 0; int dp[2550][2550]; //分别表示开始和终止，用矩阵一半的地方表示 for (int i = 0; i < n; i++) dp[i][i] = 1; for (int i = 0; i < n - 1; i++) dp[i][i + 1] = (s[i + 1...

#include <iostream> #include <cstring> using namespace std; const int N = 310; string a, b; int dp[N][N], maxx = 0, res = 0; // dp就是我们的那个表格，maxx是我们的最长的地方，res是我们的a字符串的尾 void solve() { for (int i = 0; i < a.size(); i++) { if (a[i] == b[0]) dp[i][0] = 1, maxx = 1, res = i; else dp[i][0] ...

/*dp解法 https://blog.nowcoder.net/n/e55d890d86e441208bbcbee541697e0c?f=comment 以adadd为例 第一个循环记录字母本身，如a开始到a，为1，d开始到d，为1 第二个循环记录相邻的字母是否会回文，如ad不行记录为0，dd可以，记录为2 （为什么需要记录相邻字母：因为相邻字母之间没办法在遍历中使用dp） 第三个循环dp，对于dp[i][j]，也就是从第i个到第j个字符串是否回文，首先要第i个字符和第j个字符相等，然后要第i+1个字符到第j-1个字符是回文，如果满足，则等于dp[i+1][j-1]+2 第四个循环寻找最长回...

#include <bits/stdc++.h> using namespace std; int main() { int nums=0; string s; getline(cin,s); for(char c:s){ if(c>=65&&c<=90) nums++; } cout<<nums<<endl; return 0; } // 64 位输出请用 printf("%lld")