#include <bits/stdc++.h> using namespace std; const int ms = 1e5+5; const int inf = 0x3f3f3f3f; int m[ms], f[ms]; int isEmpty[ms]; int dp[3005][3005][2][2]; main() { int n; cin >> n; int qntM = 0; for(int i = 0; i < n; i++) { cin >> m[i] >> f[i]; qntM += m[i]; } if(qntM ==...

前缀进行排序处理如何就可以保证答案的正确性呢?比如前面有一个子集,既然有那个子集,那么就一定子集中不存在前缀,如此我来了一个新的变量,我如何证明那个子集中不含有我的前缀呢?一个很显然的结论,假如存在我的前缀,那么这个集合中的任何一个都不包含这个前缀,假如这个前缀不是最后面的那个集合.那么就会出现一个什么问题呢?很显然顺序是已经确定了的,我最后一个元素一定比出现前缀的那个集合要大,而且我肯定不能包含那个集合,也就是说,我一定在它结尾的时候就比它大,而它后面的那个包含这个前缀的就一定比最后一个元素小,如此就矛盾了...可能文字有些看不明白举个栗子就好了,这个集合假设说包含的前缀是1234 而我最后...

/.../发现新博客无法传照片,且洛谷博客管理是真的..还是牛客好..设f[i][j][k]为前k种颜色填了任意i行j列..最后的答案就是f[i][j][c]的和...emm/这个怎么转移呢?我们还需要一个数组,设g[i][j][k]为k个数量填了任意i行j列的方案数.如此状态转移即可写出来了..ac代码如下: #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+9; const ll N=35,M=255; ll f[N][N][N],g[N][N][M]; in...

博客不更了

凡是背包裸题,二进制随便套.. #include <bits/stdc++.h> using namespace std; const int N=1e4+5,M=3e5+4e4; int t[M],c[M],p[M]; int id,n; int T[M],val[M]; int f[M]; inline void init() { for(int i=1;i<=n;i++) { int vnt=1; while(true) { if(p[i]-vnt<0) { val[id]=c[i]*p[i]; T[id]=t[i]*p[i]; id++; break; } el...

#include <bits/stdc++.h> using namespace std; const int N=505; int a[N]; int sum[N]; int fmx[N][N];//区间l~r的最大得分 int fmn[N][N];//区间l~r的最小得分 int main() { int n; cin>>n; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); a[n+i]=a[i]; } for(int i=1;i<=2*n;i++) sum[i]+=sum[i-1]+a[...

不难又挺有收获的一个线性dp...细节很多~很好的一个dp题代码如下: #include <bits/stdc++.h> using namespace std; const int N=10002,M=2005; bool vis[N];//表示这个点有没有管道. int x[N],y[N];//可以上升多少 可以下降多少 int l[N],h[N];//最低点 最高点. int f[N][M];//表示到了i,最少需要按多少次才能到j的高度. int main() { int n,m,k,a,b,c; cin>>n>>m>>k;//m是高度....

不是所有dp都不卡边界= - =比如这个边界就很卡 #include <bits/stdc++.h> using namespace std; const int N=105,M=10,inf=2e9+1; int sum[N]; int Fmax[N][N][M];//区间l~r中分i段能获得的max int Fmin[N][N][M];//区间l~r中分i段能获得的max inline int cnt(int x) { return (x%10+10)%10; } int main() { int n,m; scanf("%d%d",&n,&...

#include <bits/stdc++.h> using namespace std; const int N=55,M=105; int f[M][N][N]; int a[N][N]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } //可以证明第二个纵坐标一定大于第一个 for(int i=3;i<=(n+m-1);i++) { for(int j=1;j<=min...

高精度部分就不写了,太难写了.因为每行取数都是不影响的,所以直接区间dp处理每行即可. #include <bits/stdc++.h> using namespace std; const int N=85; int f[N][N]; int a[N]; inline int qp(int a,int b) { int res=1; while(b) { if(b&1) res*=a; a*=a; b>>=1; } return res; } int main() { int n,m,ans=0; cin>>n>>m; for(int ...

又是一个当初没学会的dp模型.也就是分组背包... #include <bits/stdc++.h> using namespace std; const int N=65,M=4e4; struct vv{ int price,val,team; }a[N]; int f[M],g[M]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d%d",&a[i].price,&a[i].val,&amp...

= - =又是一个新东西,不合法的可以直接转移...dp还是简单 #include <bits/stdc++.h> using namespace std; const int N=105; int a[N]; int f[N][N][2];//到了第i个没填j个偶数数这个点填奇数/偶数 int main() { int n,ans=0; cin>>n; memset(f,0x3f,sizeof f); for(int i=1;i<=n;i++) scanf("%d",&a[i]); if(a[1]==0||a[1]%2==1) f[1...

dp思路并不是那么明显,那么我们来思考下怎么贪心.首先对于一种左右两边奇偶性相同的坑,无非就两种填法,一种是拿一种和它们颜色相同的全部填满,另外一种就是随便填填代价为2.然后对于两边奇偶性不同的坑呢?无论你怎么填代价都为1吧?如此贪心的思路就很简单了.你先把那些等于偶数的坑和等于奇数的坑小的全部填了,然后剩下就是计算有几个坑了..注意边界.代码如下: //那种小点的模拟,用你的思维一步一步实现,不要急于整体实现..不然代码就会变得难写,尤其对于我这种菜鸡选手 #include <bits/stdc++.h> using namespace std; struct vv{ int w...

这题是区间dp的经典题目,和石子合并一样,但是我忘了石子合并了,毕竟我是当自己大一啥都没学,只是接触过,现在重学来的~..说实话,因为解除了许多区间dp,但是以前对于有环的只知道×2,然后是用小区间更新大区间,但是一直没理解过它们,以至于简单的区间dp都没写出来,丢人...(主要是主观意识太强了,不理解,不会,就没深想)合并一个区间会发生什么?似乎很简单吧...就是两个区间的中间那个元素没了,然后产生的价值...然后就可以很简单的转移了...好菜啊!!!代码如下: #include <bits/stdc++.h> using namespace std; const int N=2...