哒哒哒哒哒

分类

最小生成树(1) 最短路(1) 未归档(121) 题解(2)

/ 注册

全部文章（共125篇）

P1387 最大正方形 dp

思路: i j的最大正方形等于min(他的斜上方的的最大正方形,他的上方有的连续1，他的左方有的连续1)+1 #include<bits/stdc++.h> using namespace std; const int INF=10000000; int mp[205][205...

2018-10-31

0 409

P1508 Likecloud-吃、吃、吃

数字金字塔3条路 f[i][j]=max(max(f[i-1][j],f[i-1][j-1]),f[i-1][j+1])+a[i][j]; #include<bits/stdc++.h> using namespace std; const int INF=10000000; i...

2018-10-31

0 306

P1282 多米诺骨牌 dp

思路：dp[i][j] 的j是上半段的和的值这里表示的是达到上半段值是j的最小次数答案在最小的可达到的j #include<bits/stdc++.h> using namespace std; const int INF=10000000; int a[10000]...

2018-10-31

0 402

P1140 相似基因最长公共子序列

思路类似于最长公共子序列把一段基因和另外一段基因匹配不够长的用空基因替换 #include<bits/stdc++.h> using namespace std; const int INF=10000000; int dp[10000][10000]; const in...

2018-10-31

0 370

P1880 [NOI1995]石子合并区间dp+拆环成链

思路：一道经典的区间dp 唯一不同的时候终点和起点相连所以要拆环成链只需要把1-n的数组在n+1-2*n复制一遍就行了 #include<bits/stdc++.h> using namespace std; const int maxn=10005; int dp...

2018-10-31

0 414

P1280 尼克的任务 dp

思路：倒着DP f[i]表示i时刻的空闲时间最大值在当前时间没有任务开始 f[i]=f[i+1]+1; 上一分钟最大空闲时间+1 在当前时间有任务开始 f[i]=max(f[i],f[i+a[sum]) // i+a[sum]表示做完任务后的最大空闲时间因为做任务的时候...

2018-10-31

0 372

P1091 合唱队形最长上升子序列

思路：最长上升子序列正着做一遍倒着做一遍然后取最大值 #include<bits/stdc++.h> using namespace std; const int maxn=105; int dp[maxn],dp1[maxn],a[maxn]; int main(){ ...

2018-10-31

0 335

P1020 导弹拦截

思路：贪心思路拿比飞来的导弹高并且高度和飞来的导弹最相近的拦截系统去接，如果全部都比导弹矮，那就新开一个拦截系统 #include<cstdio> #include<string.h> #include<iostream> using namespac...

2018-10-31

0 273

P1064 金明的预算方案

思路：就是一个背包问题因为数据范围小，所以不把 1个带附着物的东西拆成带1个带2个或不带 #include<bits/stdc++.h> using namespace std; const int maxn=30000+10; int f[maxn]; int zhuj...

2018-10-31

0 474

Educational Codeforces Round 53 (Rated for Div. 2) D. Berland Fair

题意：一个人有T块钱有一圈商店分别出售不同价格的东西每次经过商店只能买一个并且如果钱够就必须买这个人一定是从1号店开始的！（比赛的时候读错了题，以为随意起点。。。）问可以买多少个思路：这个人有T块钱走一圈之后可以买num个花了sum块钱那么走第二圈的时候能买的东...

2018-10-31

0 375