Charlesss

未归档

ACM_RMQ(2) ACM_二分(5) ACM_二分图(8) ACM_前缀和(1) ACM_动态规划(18) ACM_干货(6) ACM_并查集(3) ACM_拓扑排序(2) ACM_搜索(24) ACM_最短路(14) ACM_树(1) ACM_树状数组(2) ACM_生成树(8) ACM_线段树(3) ACM_覆盖问题(2) ACM_连通图(2) CodeForces(131) 第九届蓝桥杯(2) 算法(3) 补题补题补题(55) 题解(3)

/ 注册

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

HDU 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活(多重背包裸题)

一道多重背包的裸题，想看详解的可以看这篇博客传送门(Coins) AC代码： #include <iostream> #include <cstring> #define MAX(a,b) a>b?a:b #define MAXN 100000...

2018-02-10

0 717

HDU 2844 Coins (多重背包+二进制优化)

首先这是一道多重背包的裸题，题意在代码中的注释里有。多重背包就是所给的物品是有限的(任意个)，我们则可以把多重背包的问题转换成01背包和完全背包来求解。首先我们先把01背包和多重背包的过程封装成函数，需要用的时候传参过去就好了，然后我来解释一下什么时候用01背包，什么时候用完全背包。我...

2018-02-10

0 363

NYOJ 311 完全背包(恰好装满)

就直接上代码吧，至于判断恰好装满问题可以看下这篇博客传送门(Piggy-Bank) 需要注意的是直接调用max函数会TLE，所以以后还是不要懒省事的直接调用max函数吧。 AC代码： #include <iostream> #include <cstring> #inclu...

2018-02-10

0 463

HDU 1114 Piggy-Bank(完全背包+恰好装满)

就以这道题来简单讲解一下完全背包问题，首先完全背包和01背包的区别在于01背包每样物品只有一个，用完了就不能再用了，而完全背包的物品是有无限个的，所以完全背包又衍生出能不能把背包恰好装满的问题。能否恰好装满问题对dp数组初始化的时候做点改变就行了。下面是完全背包的核心...

2018-02-10

0 441

HDU 2546 饭卡(01背包+预处理)

这是一道01背包问题，但是需要预处理一下，因为当你的钱不够5块钱的时候，你什么都买不了，所以直接输出钱数，当你的钱大于5块钱的时候，你可以先拿出来5块钱，留着最后去买最贵的菜，现在你剩下m-5块钱，排个序把最贵的留在最后,然后就用01背包把这m-5尽量装满(遍历1~n-1种菜，因为n是...

2018-02-08

0 432

CodeForces 919A Supermarket(水题)

英语渣表示不想说话... AC代码： #include <iostream> #include <cstdio> using namespace std; int main() { int n,m; double price; while(scanf...

2018-02-08

0 500

NYOJ 21 三个水杯(bfs模拟)

这道题是一道bfs的题，主要是怎样把倒水的过程模拟出来，一共三个杯子，六种情况(A->B，A->C，B->A，B->C，C->A，C->B)，所以我们可以用两个for循环模拟这六种情况。而在倒水的过程中又有两种情况，一是倒不满，二是倒完有剩余，这两种...

2018-02-06

0 594

Hdu 2612 Find a Way(双点bfs)

题意代码最后的注释里有，这道题就是对两个人分别进行bfs搜索，然后记录下这两个人到每一家KFC的步数，最后遍历地图求出最少的步数，思路很简单，但实现起来可能不是很好想。 AC代码： #include <iostream> #include <queue>...

2018-02-06

0 359

NYOJ 19 擅长排列的小明(dfs递归)

这道题和组合数那道题我觉得差不多，两道题可以一起写一下，对比一下，能更好的理解递归思想。 AC代码： #include <iostream> #include <cstring> using namespace std; const int MAXN = 5050;...

2018-02-06

0 391

NYOJ 58 最少步数(dfs或者bfs)

这道题最开始是用dfs做的，后来学会了bfs以后有一次用bfs做了这道题，但是奇迹般的TLE了，当时还纠结了半天最少步数竟然不能用bfs做吗？然后刚刚又用bfs交了一次，又奇迹般的AC了，这道题可以当作bfs的模板了。下面把bfs和dfs的代码都贴上吧。 AC代码（DFS）： ...

2018-02-06

0 499