ACM

HDU 1085 Holding Bin-Laden Captive!(数学,母函数)

HDU 1085	Holding Bin-Laden Captive!(数学,母函数)
给出你定值硬币的数量,问你这些硬币不能组成的最小价值是多少。这个题嘛,乱搞,dp,找规律都行,但是学长说这个用母函数做。。。乱搞代码:StatusAcceptedMemory1560kBLength486LangG++#include <iostream> #include <cstdio> using namespace std... 继续阅读 »
ACM

HYSBZ - 1042 硬币购物(dp+容斥)

HYSBZ - 1042 硬币购物(dp+容斥)
题目都看得懂,我们先谈dp再谈容斥。dp的思想就是,先假设每个硬币都不限制数量(给出一个最大界限数量即可),然后统计他们能组成的付款方法有多少种。状态转移方程为:dp[j] = dp[j] + dp[j-c[i]]意思就是,组成当前j元付款方法的方式数是在j原有的方法上加上一个 不加当前硬币的方法数。(有点绕口,自己想想就明白了。)然后接下来理解容斥。这里的容斥方法是先假设每种硬币的数量都超出了给... 继续阅读 »
ACM

2016HUAS_ACM暑假集训5 - F - Monkey Banana Problem

2016HUAS_ACM暑假集训5 - F - Monkey Banana Problem
从上往下找能连起来数字之和最大的。DP。分两部分dp比较方便,上面判断条件和下面有点区别,毕竟倒三角。题目:飞机票直达(F - Monkey Banana Problem)代码:Memory: 1784 KBTime: 68 MSLanguage: C++Result: Accepted#include <iostream> #inc... 继续阅读 »
ACM

2016HUAS_ACM暑假集训5 - C - Common Subsequence

2016HUAS_ACM暑假集训5 - C - Common Subsequence
求公共子字符串的最大长度问题,当然是DP了。题目:飞机票直达(C - Common Subsequence)代码:Memory: 5716 KBTime: 46 MSLanguage: C++Result: Accepted#include <iostream> #include <cstdio> #inclu... 继续阅读 »
ACM

2016HUAS_ACM暑假集训5 - A - Super Jumping! Jumping! Jumping!

2016HUAS_ACM暑假集训5 - A - Super Jumping! Jumping! Jumping!
求递增子字符串的最大和,注意是最大和,子字符串不一定最长,这个WA了。比如:4 1000 1 3 4, 最大是1000, 而不是1+3+4, 比如:4 1 4 3 1000 应该是 1 + 4 + 1000 = 1005题目:飞机票直达(A - Super Jumping! Jumping! Jumping!)代码:Memory: 1732 KBTime: 15 MSLangu... 继续阅读 »
ACM

2016HUAS_ACM暑假集训5 - J - Max Sum

2016HUAS_ACM暑假集训5 - J - Max Sum
求连续子序列的最大的和,因为输出的时候Case后面的数值没变化WA了一次,我竟然没看出来?题目:飞机票直达(J - Max Sum)代码:Memory: 2900 KBTime: 31 MSLanguage: C++Result: Accepted#include <iostream> #include <cstdio... 继续阅读 »
ACM

2016HUAS_ACM暑假集训5 - G - 湫湫系列故事——减肥记I

2016HUAS_ACM暑假集训5 - G - 湫湫系列故事——减肥记I
经典完全背包问题。把幸福度看成价值,把卡路里看成重量,求卡路里刚好满足需求时的最大幸福度。题目:飞机票直达(G - 湫湫系列故事——减肥记I)代码:Memory: 2516 KBTime: 46 MSLanguage: C++Result: Accepted#include <iostream> #include <c... 继续阅读 »