这里学到的东西主要是一个是 return true放的位置，第二个是学会拆解函数 #include<iostream> #include<bits/stdc++.h> using namespace std; bool isprime(int x) { if(x<2) return false; for(int i=2;i<=x/i;i++) { if(x%i==0) return false; } return true; ...

这道题题目的题解简直就是绝妙：位或运算的本质是什么，位货运算的本质是确定两个中是否又一个是真的状态，并且保持原有的状态。

极其好玩的五种动态转移问题 //将手上的牌分成两部分，如果两部分点数相同那么就得到这两部分的牌。 //在开始之前还可以全选一些牌将其点数增加二倍。最后要value最大的方式。 //状态转移一共有五种情况： //1、不选当前的卡片：dp[i][j][k] = dp[i-1][i][j]; //2、选当前的卡片但将其放到点数大的那一个里面(不使用技能)：dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k+a[i].point]+a[i].v) //4、选当前的卡片但将其放到点数小的那一个里面(不使用技能)：dp[...

超级有意思的一道动态规划区域赛真题：

没想到做了一道ICPC的原型题目 这道题居然有5种转移状态 //将手上的牌分成两部分，如果两部分点数相同那么就得到这两部分的牌。 //在开始之前还可以全选一些牌将其点数增加二倍。最后要value最大的方式。 //状态转移一共有五种情况： //1、不选当前的卡片：dp[i][j][k] = dp[i-1][i][j]; //2、选当前的卡片但将其放到点数大的那一个里面(不使用技能)：dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k+a[i].point]+a[i].v) //4、选当前的卡片但将其放到点数小的那一个里面(不使用技能)：dp[i][j][k] ...

在背包问题中，当我们使用map（或unordered_map）来存储动态规划的状态时，我们实际上是在实现一种离散化的过程。离散化是一种数据预处理技术，用于将大范围的数值映射到较小的、连续的范围内，以便更有效地存储和计算。 在背包问题中，背包的容量通常是一个较大的整数范围，但如果不是所有的容量都会被实际使用到（即，不是所有的物品组合都会导致每个可能的容量被访问），那么使用数组来存储DP状态将会非常浪费空间。而map（或unordered_map）则提供了一种按需分配空间的方式。 具体来说，当我们尝试更新一个背包容量为j的状态时，我们首先检查dp[j]是否已经被创建。如果j还没有被访问过，那么d...

比较疑惑的是这一点主要是 #include "iostream" #include "algorithm" using namespace std; int V[26]; int W[26]; long long int dp[26][30001]; int main() { int N,n,i,x; cin>>N>>n; for(i=1;i<=n;i++){ cin>>V[i]>>W[i]; } for(i=1;i<=n;i++){ for(int j=N;j...

map<int, int>::iterator it = dp.end(); it--; cout<<(*it).second; 标准的套用格式问题，需要注意

这次又死在了数组数据开的范围上，下次应该注意 #include<bits/stdc++.h> using namespace std; const int N=1000; int t[101]; int w[101]; int dp[101][1001]; int main() { int T,M; cin>>T>>M; for(int i=1;i<=M;i++) { cin>>t[i]; cin>>w[i]; } for(int...

很奇怪的一道题，这样做居然要过不去 居然不压成一维就对了，其他情况就错了 #include<bits/stdc++.h> using namespace std; const int N=20000; int a[N]; int dp[N]; int main() { int v,n; cin>>v>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } for(int i=1;i<=n;i++) { ...

没想到这里能做到一道经典的LCS经典的模板问题 //经典的求解两个序列的最长公共子序列的长 //LCSd的经典模版问题 #include <bits/stdc++.h> using namespace std; const int maxn = 5000+10; int dp[maxn][maxn]; string s1, s2; int main() { while (cin>>s1>>s2) { if (s1[0]==s2[0]) dp[1][1] = 1; // memset(dp,0,sizeof(dp)...

//这是我看的一篇写的稍微通俗易懂的题解了，引用自牛客273087142号大佬的题解，之前没有加引用，非常抱歉 #include<iostream> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const int N = 1e5 + 10; int n, sz[N * 2], res; // sz[i]表示点i有多少个儿子 int h[N], e[N * 2], ne[N * 2], idx; bool st[N * 2]; voi...

vector数组+pair对象+x.first与x.second的联合使用 牛客上开始写题解的第一天 ">#include<bits/stdc++.h> #include<vector> using namespace std; typedef pair<int,int> PII; vector<PII> s; const int N=1e5+10; int prime[N]={0}; int a[N],b[N],g[N],k[N]; int main() { int n; cin>>n; for...