UVa 1218 Perfect Service dp：树上dp 状态转移方程的优化
UVa 1218 Perfect Service 树上dp 状态转移方程的优化 The question is from here. 与这个题目 UVa 1220 Party at Hali-Bula dp：树的最大独立集写法很像，虽然各有不同； My Solution 状态定义：d[u][0] 表示u是服…
UVa 1220 Party at Hali-Bula dp：树的最大独立集
UVa 1220 Party at Hali-Bula dp：树的最大独立集 The question is from here. My Solution 注意点：这个题目有些测试数据是先出现father再出现son的，如 5 jack jill black black jack kar pur pur black …
UVa 12186 Another Crisis dp：树上dp
UVa 12186 Another Crisis 树上dp The question is from here. My Solution d(i)表示给上级发信至少需要多少工人。把所有子结点的d值排序然后取前c个， 对除非的处理 ★★ c = (k*T - 1) /100 +1; 用前向星储存树 每…
UESTC 1137 邱老师选妹子 dp：？这个难道不是暴力法
邱老师选妹子 dp：这个难道不是暴力法 Source 2015 UESTC Training for Dynamic Programming The question is from here. My Solution 暴力法分分钟过，只是不知道为什么，这个是在dp专题，☺☺ 暴力的话 10^6*6…
UVa 10003 Cutting Sticks dp : 线性dp triangulation三角剖分
UVa 10003 Cutting Sticks 线性dp triangulation三角剖分 The question is from here. My Solution 线性dp 三角剖分类题目的经典吧， 状态：d[ i ][ j ] 表示切割 i - j 这一段的最小费用 ，0 <= i < j <=…
UESTC 1131 男神的礼物 dp：最优矩阵链乘 triangulation 双dp
男神的礼物 最优矩阵链乘 triangulation 双dp Source 2015 UESTC Training for Dynamic Programming My Solution 这是一个经典的最优矩阵链乘问题，只不过单个费用会改变，像是2个dp搞在一起，是把单个的min…
UVa 11584 Partitioning by Palindromes 线性结构上dp LIS
UVa 11584 Partitioning by Palindromes 线性结构上dp LIS The question is from here. My Solution d[ i ] = min{ d[ j ]+1 | is[j+1][i]是回文串 }; d[ i ] 表示0~i 内回文串的最小个数; 然后对于is[ j+1 ][ i ]…
UVa 12563 Jin Ge Jin Qu hao 0-1背包问题
UVa 12563 Jin Ge Jin Qu hao 0-1背包问题 The question is from here My Solution： 刘老师给了我们那么多的数据是为了告诉我们: 歌曲的总时间不会超过 n*180-1+678 及 50*180-1+678 = 9677 并不像题中的t <= 1…
UESTC 766 乐乐和球球 博弈 暴力(也可以不用暴力法)
乐乐和球球 博弈 暴力(也可以不用暴力法) My Solution 首先 N>=K 的情况应该是 拿空N-K 然后加上 C 当 N=C 则，为C 如果 (K/N)*N=C 则 i+C 如果t…
UESTC 1251 谕神的密码 贪心
谕神的密码 贪心 Source 第七届ACM趣味程序设计竞赛第二场（正式赛）B My Solution w9=s/9; y9=s-w9*9; 贪心， 最大的前面999....y9...最小的前面为1.......y9 99999 主要是上面这样，然后有几个地方y9=…
UESTC 1262 Memory 暴力法
Memory 暴力法 Source 第七届ACM趣味程序设计竞赛第三场（正式赛）E My Solution 思路是已经有i-1个满足条件的数，再加第i个数进去依然满足，任意两个数的和不会和另外的两数和相等。 前面比赛的时候一直以…
UESTC 1264 人民币的构造 数论
人民币的构造 数论 Source 第七届ACM趣味程序设计竞赛第三场（正式赛）C My Solution tem+sum是当前的最大可以构出的值。 否则tem=sum;tem=2*(tem+sum)+1;新的最大值是tem+sum 1,3,9开始找规律1只能1，1、…
UESTC 1265 宝贵资源
宝贵资源 新手题 Source 第七届ACM趣味程序设计竞赛第三场（正式赛）A My Solution 看清楚是正方形好了，第一没注意就交了，浪费了20min的罚时，o(︶︿︶)o 唉新手嘛。 #include #include using namesp…
UESTC 1255 斓少摘苹果 贪心
斓少摘苹果 贪心 Source 第七届ACM趣味程序设计竞赛第二场（正式赛） C My Solution 第一想法是模拟，应该超时 只有最后一次可能是不到m个苹果 其它时候都是每次m个 所以总数sum，次数可能为(sum-1)/m+1…
UESTC 1253 阿里巴巴和n个大盗 博弈、策略
阿里巴巴和n个大盗 博弈、策略 Source 第七届ACM趣味程序设计竞赛第二场（正式赛） D My Solution 首先总人数是n+1人。 由于必须半数以上人同意才能通过方案，所以当剩余两个人时2号必死，因为1号…
UESTC 1256 昊昊喜欢运动 n^2的预处理 or 前缀和
昊昊爱运动 n^2的预处理 or 前缀和 Source 第七届ACM趣味程序设计竞赛第二场（正式赛） A My Solution 1、当时把时间改成3000MS 所以直接暴力，过去，用一个数字cot[108]，来记录每个区间…
UESTC 1024 Flying Chess 注意那个 1
Flying Chess 注意那个 1<x<N 不是1<=x<N 模拟 My Solution 十分钟左右就把题目搞完了，然后，明明觉得自己对的，却是不对的，找bug找了好久，才发现 那个 1<x 把前面错掉的程序中a==b改为…
UESTC 58 任意阶矩阵的乘法 新手题
虽然简单但优化还是要思考一下的 ， 而且也使自己意识到了原来没有注意的问题。 1、memset(,,);还是比较耗时间的，特别是数组河大的时候； 2、有些不用置零的数字就不要总是置零了； 任意阶矩阵的乘法 新…
UESTC 1013 我的魔法栈 贪心
我的魔法栈 贪心 My Solution 最前面做的时候直接模拟了，虽然正确，但确实时间超出了，☺ ☺☺☺☺☺ 写几组，总结一下规律 #include #include using namespace std; const int maxn=10008; char ch[maxn]; …
UESTC 1033 Marineking wilyin 新手数学题
Marineking wilyin 新手数学题 My Solution 推导一下数学公示，解决数学问题 #include #include #include using namespace std; //用到了白书数据结构-例题6-5中，我自己学到的小技巧。 void jiaohu…
