背包常规解法：
物品
０__１ __２ __３ __４ __５ __.. __ __ __ __ __ __ __ __
|__ __装
|__ __不装
dfs( int[] prices, int [] weights, int curW, int curP, int idx, int &maxN) {
//不装
dfs(prices, weights, curW, curP, idx+1, maxN)
//装
maxN ＝ max( curP+ prices[idx] )
dfs(prices, weights, curW+weights[idx], curP+prices[idx], idx+1, maxN)
}
能处理 2^idx < MAXINT 的情况
dp(int[] prices, int [] weights, int &maxP[ int maxW ] ){
maxP[0] = 0
repUp(i, 0, N-1)
repDown(j, maxW, weights[i])
maxP[j] <= maxP[ j-weights[i] ] + prices[i] //试装ｉ
能处理idx*maxW < MAXINT
http://www.cnblogs.com/yuris115/p/3537540.html
这道题，无重量限制求可达价值的背包DP, maxP换成bool t[ int MOD=77077 ]，
for i=1 to N:
for j=0 to MOD-1:
tmp[ j*a[i]%MOD ] || = t[j]
t = tmp
处理 idx*MOD < MAXINT
Problem Statement |
|||||||||||||
|
A spell is defined by its incantation, the word spoken when the spell is being cast. If you know the incantation of a spell, you can create counterspells in the following manner. First, you can optionally delete any number of characters from the original incantation. Note that empty incantations are not valid so you cannot delete all characters. Then, you can replace any number of the remaining characters according to a set of replacement rules. The replacement rules tell you which letters can be replaced, and the letters with which they can be replaced. For example, if the original incantation is "AA" and the allowed replacement is 'A' to 'Z', the following counterspells are possible: "AA", "A", "Z", "ZZ", "AZ", "ZA". The best counterspell is the one with the greatest power. The power of a spell is the product of all its character values modulo 77077, where the value for a character is its position in the alphabet (character 'A' has value 1, character 'B' value 2, character Please note that if the allowed replacements are 'A' to 'B' and 'B' to 'C', the counterspell for "AB" is "BC" not "CC". You cannot change a character that has already been changed, even if it would lead to a more powerful spell. You will be given a string spell, the incantation of the spell you are going to counter, and a string rules, the allowed replacements for letters. The first character in rules is the allowed replacement for |
|||||||||||||
Definition |
|||||||||||||
|
|||||||||||||
Limits |
|||||||||||||
|
|||||||||||||
Constraints |
|||||||||||||
| - | spell will contain between 1 and 13 characters, inclusive. | ||||||||||||
| - | spell will contain only uppercase letters ('A'-'Z'). | ||||||||||||
| - | rules will contain exactly 26 characters. | ||||||||||||
| - | rules will contain only uppercase letters ('A'-'Z') and dashes ('-'). | ||||||||||||
Examples |
|||||||||||||
| 0) | |||||||||||||
|
|||||||||||||
| 1) | |||||||||||||
|
|||||||||||||
| 2) | |||||||||||||
|
|||||||||||||
| 3) | |||||||||||||
|
|||||||||||||
| 4) | |||||||||||||
|
|||||||||||||
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited.
(c)2003, TopCoder, Inc. All rights reserved.
这是一个牛人的代码，我重写了一遍。第一次发现原来DFS还能这样用，给我很大启发，还有一点就是数论部分我学的太烂了，最近还是要补补。当然，这里不止用DFS这一种办法，你可以把它展开……:-D