题目：   思路： 这题的思路当然就是枚举每个释放魔法的地方啦，然后检查这片区域有没有建筑，有的话就要停止施法，++ans。假设我们要施法的区域是下面这个红区域，检查红区域内有无建筑就好  二维前缀和介绍： 当然如果直接暴力的话复杂度 那绝对爆炸的,这里就要引入二维前缀和了，sum[ i ][ j ]表示（0，0）到（i，j）的前缀和。先给出递推公式 sum[ i ][ j ] = map[ i ][ j ]+sum[ i-1 ][ j ]+sum[ i ][ j-1 ]-sum[ i-1 ][ j-1 ]   看图就知道了，sum[i][j] 表示的是蓝区域红区域加黄区域再加右下角那个 su...

题目：   思路 题意就是 建立一棵中序遍历为 （1，2，3，....,n）的树，求 的最大值 如果是叶子结点 值就是 如果只有左子树 值就是 如果只有右子树 值就是 如果左右子树都存在 值就是  ps：这里题意不明，题目说“若以某个子树为主，规定其加分为1”我实在是没看懂，还是问了队友才知道什么意思 有了上面那个递推式就知道这是区间dp了，dp[i][j]表示i到j是一棵树的最大值所以转移方程就是 ： dp[ i ][ j ] = max(dp[ i ][ j ] , dp[ i ][ k - 1 ]*dp[ k + 1 ][ j ]+tree[ k ] ) 这里的k表示以k为根 这里有两种...

题目   思路  题目大意就是n个石墩，m个荷叶，石墩可以站很多青蛙，荷叶只能站一个，青蛙过河后不能回去，青蛙必须按照汉诺塔站在石墩上，求最多的过河青蛙数。  先假设 n == 0，那就让每个青蛙都在一个荷叶上，初始石墩剩一个青蛙直接过河，能过m+1个青蛙 然后 n == 1 ，让每个青蛙都在一个荷叶上，初始石墩青蛙跳到河和中间石墩，其他荷叶青蛙跳到河中间石墩，问题就变成 n==0了，所以答案就是 （m+1）* 2 再分析 n == 3 ，中间石墩假设为 A，B，先让青蛙都跳满荷叶，全部到A上，然后初始石墩青蛙再这样跳满荷叶，再全部到B上，然后A的青蛙跳到荷叶上，再全部跳到B上，这样B上就有（...

#include<bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define pb push_back typedef long long ll; #define SZ(x) ((ll)(x).size()) typedef vector<ll> VI; typedef pair<ll, ll> PII; const ll mod = 1000000007; ll powmod(ll a, ll b) { ll res = 1; a %= mo...

Question   Analysis 这题如果数据范围再小一点的话很明显可以用dp求解，大概就是这样： bool vis[maxn];//位置i有无石子 int dp[maxn];//到达位置i的最小踩石子数 fill(dp,dp+maxn,INF);//全部初始化为最大 dp[0] = 0; for(int i = 1 ; i <= L ; ++i){ for(int j = s ; j <= t ; ++j ){ if(i >= j) dp[i] = min(dp[i],dp[i-j]+vis[i]); } } 但是L的范围是1e9，直接算会爆内存的，所以就想到了离散化...

题意 n个城市走m次，问走的路程最短 思路 看完题目还以为是找两个城市最短距离乘 m ，看到有初始位置我还是太年轻了。因为有初始位置，那在初始时可能有两种情况： 1.走到左边的城市 2.走到右边的城市。这两种情况要分别讨论。走到任意一个城市后有三种情况： 1.和左边的城市来回走完m次 2.和右边的城市来回走完m次 3. 往左走到一个城市或往右走到一个城市 。这三种情况直接模拟就好，不过要注意边界 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f c...

前面的碎碎念，每次每日一题看完题目感觉没思路就忍不住去瞄雨巨的题解，看完就感觉啥都会了，老这样是不是没提高啊 思路 dp[ i ][ 0 ][ 0 ]第i个位置 无火，第i+1个位置 无 火dp[ i ][ 0 ][ 1 ]第i个位置 无 火，第i+1个位置 有 火dp[ i ][ 1 ][ 0 ]第i个位置 有 火，第i+1个位置 无 火dp[ i ][ 1 ][ 1 ]第i个位置 有 火，第i+1个位置 有 火这样就很容易可以写出状态转移方程了，都在代码里我就不在这写了 代码 #include<bits/stdc++.h> using namespace std; typede...

题意：  求n * n的网格图横竖对称的填法 思路： 假设是个n * n的网格图，如果第一行放在第一列那就剩下的（n-1） * （n-1）化简问题 ， 如果第一行放在第二列 ， 那第二行的位置也就固定了，剩下（n-2） * （n-2），同理第三第四。。。。，除去第一行有 n - 1 行 所以可以得出dp[ i ] = dp[ i - 1 ] + （i-1）*dp[ i - 2 ] 代码 #include<bits/stdc++.h> using namespace std; typedef long long ll; ll dp[100005]; int main(){ dp[0]...

A 打怪 题目描述戳我传送 你是一个勇士，现在你准备去森林刷毛球怪，你有两个属性（血量，攻击力），毛球怪也有这两个属性。当你遭遇一只毛球怪时你们会进入战斗，然后你和毛球怪轮流攻击（你先手），每次使对方的血量减去自己攻击力的数值，当一方的血量小于等于 0 时死亡。现在你想知道在自己活着的前提下最多杀死几只毛球怪。 输入描述 第一行一个正整数t，代表测试数据组数。 第二行四个正整数h，a，H，A，代表你的血量和攻击力以及毛球怪的血量和攻击力。 所有整数大小不超过1000。 输出描述 共 t 行，每行一个整数x，代表最多能杀死多少毛球怪。如果能杀死无数只，输出-1。 思路 因为是自己先出手，所以只要...

从 https://blog.csdn.net/ACdreamers/article/details/21822165 中整理所得  = F [ i + 2] -1 一些重要的公式 1、 F [ n + k ] = F [k] * F [ n + 1 ] + F [ k - 1 ] * F [ n ]2、 F [ i + 1] * F [ i - 1 ] - F [ i ]^2 = ( - 1 )^i 3、 若 n >= 1 , r >= 2 ,则 f [ n ] * f[ n + r - 1] - f[ n + 1 ] * f[ n + r - 2] = f[ r - 2 ] 4...

（个人感觉这题最难的地方是看懂题目）ps：没想到有人用sort维护都能ac，可能因为这个加强了数据吧 Solution 题意是：输入奇数个数的时候输出此时输入的数的中间值（本蒟蒻看成了输入的数是奇数），因为可能输入的数有相同的所以可以用multiset保存输入的数，对于每次输出可用迭代器寻找值为中间的数即可 做完了这题可以去试试 poj 3784 也是对顶堆的模板题 code(前解法) #include<bits/stdc++.h> using namespace std; typedef long long ll; #define INF 1e8 const int mod = ...

A. Maximize The Beautiful Value 戳我传送 Solution 题目大意是把一个数往前挪至少k位，i到i-k数往后挪，因为这是个非递减数列，要求  最大 ，显然后面的权值大于前面，所以只要把一个数往前移动k位即可，之间的数往后挪动因此用前缀和加上sum[i - 1] - sum[i - 1 - k]即可 code #include<bits/stdc++.h> using namespace std; typedef long long ll; #define INF 1e8 const int mod = 1e9+7; const int maxn =...

Solution 树上记数，dp[i][j]表示前i个位置上有j种颜色，那很自然就能推出dp[i][j] = dp[ i - 1 ][ j ] + ( k - j + 1 )*dp[ i - 1 ][ j - 1 ]。（dp[ i -1 ][ j ]是位置 i 和 i - 1 涂相同的颜色，( k - j + 1 ) * dp[ i - 1 ][ j - 1 ]是位置i和i-1涂不同颜色） code #include<bits/stdc++.h> using namespace std; typedef long long ll; #define INF 1e8 const int...