哒哒哒哒哒

未归档

最小生成树(1) 最短路(1) 题解(2)

/ 注册

全部文章 / 未归档（共121篇）

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

Educational Codeforces Round 53 (Rated for Div. 2) C. Vasya and Robot

题意：给出一段操作序列和目的地问修改（只可以更改不可以删除或添加）该序列使得最后到达终点时所进行的修改代价最小是多少其中代价的定义是终点序号-起点序号-1 思路：因为代价是终点序号减去起点序号所以在终点和起点之前可以任意变换则如果 x+y 和序列长度n的奇偶性相同 ...

2018-10-31

0 445

吉哥系列故事――恨7不成妻 HDU - 4507 数位dp

思路和普通的DP不一样的是这里求的是满足条件的数的平方的和而数位DP只跟数每位是什么密切相关所以要开一个结构（多加一个数的和sum 和平方和qsum）存一下各个状态的和的情况 dp[pos][state1][state2].num 满足该状态的数有几个 dp[pos][st...

2018-10-08

0 420