P9947[USACO20JAN]PhotoshootB题解纯模拟！在\(a_{1}\)算出来之后，我们就可以通过\(b\)数组可以求出以后\(a\)数组的所有元素。要判断是否为排列，我们可以使用一个\(vis\)做桶，为了保证字典序最小，我们可以从\(1\)开始枚举，每次枚举前要清空一下\(vis\)数组，最后使用

目录1.动态规划的介绍2.动态规划的例题第1道题数字三角形(如果想看递归写法可以到我的记忆化递归里去看看记忆化递归_将递归程序记忆化-CSDN博客)第2道题最长公共子序列(模板) 第3道题 最长上升子序列第4道题最大子段和背包系列问题01背包完全背包1.动态规划

(•̀ω•́)y好fan题解#include<bits/stdc++.h>usingnamespacestd;inlineintread(){ charc;intf=1,res=0; while(c=getchar(),!isdigit(c))if(c=='-')f*=-1; while(isdigit(c))res=res*10+c-'0',c=getchar(); returnres*f;}consti

思路由于每次输入\(x\)和\(y\)只改变其上下左右的值，所以每次只要更新其相邻的值即可。当某个位置相邻的奶牛数达到\(3\)时，舒适度加一。当某个位置相邻的奶牛数达到\(4\)时，舒适度减一。注意：每增加一头奶牛以后，如果该位置相邻正好有三头奶牛，则舒适度也要加一。ACcod

能量消耗：一个前缀和优化dp的大典题，要是数据水一点\(O(n^3)\)都能硬草过去。思路显然，定义\(dp[i]\)为考虑前\(i\)个塔，并且将前面的精灵全部收集的最小代价。于是转移：\[dp[i]=min(dp[i],dp[j]+w(j,i)+c[i])\]其中\(0\lej<i\lem\)，\(w(j,i)\)表示收集从塔\(j\)到

题意：分析：远看数论题，实则是道数据结构。记\(f_{i}\)表示\(r_{k}=i\)的方案数，\(g_{i}\)表示\(l_{1}=i\)的方案数，那么运用简单容斥，可得：\[ans_{x}=(\sum_{i=1}^{n}f_{i})-((\sum_{i=1}^{x-1}f_{i})+1)\times((\sum_{i=x+1}^{n}g_{i})+1)+1\]先考虑如何计算\(f_{i

原题链接题解一步一步来，当\(k=2\)的时候，怎么分？当\(k=2\)时，两个点集之间的距离等于两个点集中各取一个点之间的最小距离，我们联想到最小生成树的建立过程，按边权从小到大依次加入，如果两个点所属集合不同便合并因此，当\(k=2\)的时候，答案是最小生成树的最后一个合并边（树边）可

题目链接题目描述假设地球上的新生资源按恒定速度增长。照此测算，地球上现有资源加上新生资源可供\(x\)亿人生活\(a\)年，或供\(y\)亿人生活\(b\)年。为了能够实现可持续发展，避免资源枯竭，地球最多能够养活多少亿人？解题思路经典的牛吃草问题，只是换了一个问法而已。可以戳这里，也

原题链接题解思考这类问题之前先考虑完成目标有几种方法，再考虑方法的可行性code#include<bits/stdc++.h>usingnamespacestd;inta[1005],b[1005];intmain(){intn,m;cin>>n>>m;for(inti=1;i<=n;i++)cin>>a[i];for(inti=1;i<=n;i++)cin>>

力扣题目链接classSolution{staticboolcmp(inta,intb){returnabs(a)>abs(b);}public:intlargestSumAfterKNegations(vector<int>&A,intK){sort(A.begin(),A.end(),cmp);//第一步for(inti=0;i<A.size

T1洛谷P3436PRO-ProfessorSzu首先缩点。然后从所有没有入度的强连通分量开始dfs，进行dp，数一下每个点到终点有多少路径。要注意的是当且仅当一个点能够到达终点时才能够用来更新其他点的dp值。代码#include<iostream>#defineintlonglongusingnamespacestd;in

题目描述小红正在玩一个“炸砖块”游戏，游戏的规则如下：初始有一个n∗m的砖块矩阵。小红会炸k次，每次会向一个位置投炸弹，如果这个位置有一个砖块，则砖块消失，上方的砖块向下落。小红希望你画出最终砖块的图案。#include<iostream>#include<cstring>#include<algorithm>u

n*n(n<1000)的棋盘有一些亮着的灯泡,和灭着的灯泡,按行或者列可以将行或者列灯泡翻转。但是没有花费，按某一个格子也可以使灯泡的状态翻转，花费一元，问不超过k元，能否是棋盘的灯泡全亮，k<n。问是否可行及可行方案。#include<iostream>#include<cstdio>#include<cstring>#include<al

intlargestSumAfterKNegations(int*nums,intnumsSize,intk){intt[201]={0};intsum=0;for(inti=0;i<numsSize;i++){t[100+nums[i]]++;sum+=nums[i];}while(k>0){for(inti=0;i<201;i++){

原题链接题解对于每个容量，当前组\(i\)而言，放的决策有\(size(i)+1\)种code#include<bits/stdc++.h>usingnamespacestd;structunit{intw,v;};vector<unit>G[1005];intmain(){intm,n;cin>>m>>n;intlen=0;for(inti=1;i&

原题链接题解：逆序思维我们如果正着考虑戳印序列，那么题目会很复杂，但是如果我们倒着考虑，即最后按下的戳印位置一定和stamp一一对应，然后将该位置改为？后再取匹配，那么问题就容易解决了。 classSolution{public:intn,m;intsum[1005],que[1005],bol[1005];vect

难度1这题看到一点思路也没有，但是看到最小操作数想到二分，dp和贪心，二分答案的check显然不会，贪心不会。发现对于一行，前面的\(i-2\)是不会影响的，这一行也不会影响后面的\(i+2\)行，所以是dp。考虑如何设计状态因为\(i-1\)和\(i+1\)行都会影响，所以设计出来一个dp[i][0/1][0/1][0/1]的东

题目描述有一个a*b的整数组成的矩阵，现请你从中找出一个n*n的正方形区域，使得该区域所有数中的最大值和最小值的差最小。输入格式第一行为3个整数，分别表示a,b,n的值第二行至第a+1行每行为b个非负整数，表示矩阵中相应位置上的数。每行相邻两数之间用一空格分隔。100%的数据2<

题目描述如何把一个正整数N（N长度<20）划分为M（M>1）个部分，使这M个部分的乘积最大。N、M从键盘输入，输出最大值及一种划分方式。输入格式第一行一个正整数T(T<=10000)，表示有T组数据。接下来T行每行两个正整数N，M。输出格式对于每组数据第一行输出最大值。第二行输出划分方案，将N按

选课传送门树型背包，结合树型dp（dfs）和背包dp。code#include<bits/stdc++.h>usingnamespacestd;intn,m,f[1005][1005],k[1005];vector<int>son[1005];intdfs(intu){ intp=1; f[u][1]=k[u]; for(intv:son[u]) { intsiz=dfs(v); for(inti=min(m+1,p);i;

这道题被样例误导了，没想到思路，看了眼提示才做出来。代码本身很简单，关键在于能不能想到思路。Code#include<iostream>usingnamespacestd;stringsa[1005],sb[1005];intN,M,mc;intmain(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin>>N>>M; for(int

题目描述XP在机房里放了一块正三角形的大蛋糕，但是第二天他发现蛋糕被老鼠咬坏了。XP不想让蛋糕白白的被浪费，于是他把蛋糕分割成了一个个的小正三角形（如上图所示）。黑色的小正三角形表示老鼠把那一块咬坏了。XP想要切出一块最大的没被老鼠咬坏正三角形的蛋糕，可是最大的三角形有多

原题链接思路1.任意一轮出牌，只有三种选择2.每一轮的得分只与当前一轮出的牌和上一轮出的牌相关由此我们可以设\(dp[i][j]\)为第\(i\)轮，出牌\(j\)的得分3.由于扣分机制，扣的分数与扣的次数有关，所以我们再加一层\(dp\)代表扣的次数code,注意细节#include<bits/stdc++.

原题链接题解对于任意剩余塔，都可以表示为以某个塔结尾的等差数列code#include<bits/stdc++.h>usingnamespacestd;inth[1005]={0};intdp[1005][40005]={0};//代表以塔i结尾，等差为j的种类inthaxi(intx){returnx+20001;}intmain(){intn;cin>>n;

E-ChristmasColorGrid1https://atcoder.jp/contests/abc334/tasks/abc334_e思路https://www.cnblogs.com/Lanly/p/17923753.htmlCodehttps://atcoder.jp/contests/abc334/submissions/49243194inth,w;bools[1005][1005];intc[1005][1005];//c-classlongl