浠ュ墠娌℃湁閬囧埌榪囪繖鏍風殑DP棰樼洰
榪欓鍔犳繁浜嗘垜瀵逛簬“姣忎釜瀛愰棶棰樼殑絳旀閮芥槸鏈浣崇瓟妗?#8221;鐨勭悊瑙?br /> 棣栧厛鏄澶栫殑璁＄畻
灝嗚寖鍥翠互鍐呯殑騫歌繍鏁板瓧鎵撹〃
鐒跺悗浠庤緭鍏ユ暟瀛桸寮濮嬮掑噺DP璁＄畻
N鐨勬鏁頒負0
濡傛灉鏈鍚?鐨勬鏁頒負姝ｆ暟
璇存槑鏈夎В
鍐嶄粠0寮濮嬮掑瀵繪壘瑙ｇ殑璺緞
涓嶈繃榪欎釜鏂規硶鏈鍚庝篃娌℃湁閫氳繃tc鐨勭郴緇熸祴璇?br /> 鏁板瓧涓澶у氨瓚呮椂浜?br /> 鍚庨潰鍙堟椂闂村啀鐮旂┒涓涓?br /> 鐪嬬湅鏈夋病鏈夊姙娉曞湪鏀硅繘
1 import java.util.*;
2 import java.util.regex.*;
3 import java.text.*;
4 import java.math.*;
5 import java.awt.geom.*;
6
7 public class TheSumOfLuckyNumbers
8 {
9
10 public int[] sum(int n)
11 {
12 ArrayList<Integer> table = calTable();
13 int[] dp = new int[n+1];
14 Arrays.fill(dp, Integer.MAX_VALUE-10);
15 dp[n] = 0;
16 int i , j;
17 for(i = n; i > 0 ; -- i){
18 for(int lucky:table){
19 if(i - lucky >=0 && dp[i] + 1 < dp[i - lucky])
20 dp[i - lucky] = dp[i] + 1;
21 }
22 }
23 if(dp[0] == Integer.MAX_VALUE)
24 return new int[0];
25 ArrayList<Integer> ans = new ArrayList<Integer>();
26 int total = dp[0]-1;
27 for(i = 0 ; i <= n; ++ i){
28 for(int lucky:table){
29 if(i + lucky <= n && dp[i + lucky] == total){
30 ans.add(lucky);
31 i += lucky-1;
32 total--;
33 break;
34 }
35 }
36 }
37 int[] ret = new int[ans.size()];
38 for(i = 0 ; i < ans.size(); ++ i)
39 ret[i] = ans.get(i);
40 return ret;
41 }
42
43
44
45 public ArrayList<Integer> calTable(){
46 ArrayList<Integer> table = new ArrayList<Integer>();
47 table.add(4);
48 table.add(7);
49 int i = 1;
50 while(i < 7){
51 ArrayList<Integer> temp = new ArrayList<Integer>();
52 for(int j = 0 ; j < table.size(); ++ j){
53 int newItem = table.get(j) * 10;
54
55 temp.add(newItem+4);
56 temp.add(newItem+7);
57 }
58 i++;
59 table.addAll(temp);
60 }
61 return table;
62 }
63 }
2 import java.util.regex.*;
3 import java.text.*;
4 import java.math.*;
5 import java.awt.geom.*;
6
7 public class TheSumOfLuckyNumbers
8 {
9
10 public int[] sum(int n)
11 {
12 ArrayList<Integer> table = calTable();
13 int[] dp = new int[n+1];
14 Arrays.fill(dp, Integer.MAX_VALUE-10);
15 dp[n] = 0;
16 int i , j;
17 for(i = n; i > 0 ; -- i){
18 for(int lucky:table){
19 if(i - lucky >=0 && dp[i] + 1 < dp[i - lucky])
20 dp[i - lucky] = dp[i] + 1;
21 }
22 }
23 if(dp[0] == Integer.MAX_VALUE)
24 return new int[0];
25 ArrayList<Integer> ans = new ArrayList<Integer>();
26 int total = dp[0]-1;
27 for(i = 0 ; i <= n; ++ i){
28 for(int lucky:table){
29 if(i + lucky <= n && dp[i + lucky] == total){
30 ans.add(lucky);
31 i += lucky-1;
32 total--;
33 break;
34 }
35 }
36 }
37 int[] ret = new int[ans.size()];
38 for(i = 0 ; i < ans.size(); ++ i)
39 ret[i] = ans.get(i);
40 return ret;
41 }
42
43
44
45 public ArrayList<Integer> calTable(){
46 ArrayList<Integer> table = new ArrayList<Integer>();
47 table.add(4);
48 table.add(7);
49 int i = 1;
50 while(i < 7){
51 ArrayList<Integer> temp = new ArrayList<Integer>();
52 for(int j = 0 ; j < table.size(); ++ j){
53 int newItem = table.get(j) * 10;
54
55 temp.add(newItem+4);
56 temp.add(newItem+7);
57 }
58 i++;
59 table.addAll(temp);
60 }
61 return table;
62 }
63 }
]]>
瀛楃涓查暱搴﹀皬浜?00
鐩稿綋浜庡幓鎼滅儲1锝?00涓殑涓緇勪笉鍚岀殑鏁?br /> 鍔犺搗鏉ョ瓑浜庨暱搴
鍚屾椂姣忎釜鏁板瓧閮借灝忎簬絳変簬姣旇嚜宸卞皬鐨勬墍鏈夋暟鐨勫拰鍔犱竴
鍥犱負L姣旇緝灝?br /> 鎵浠ョ敤娣辨悳灝卞彲浠ヤ簡
鍦ㄨ繖涓繃紼嬩腑瑕佹敞鎰忔繁鎼滄椂鍊欓渶瑕佷粠澶у線灝忔悳
榪欐牱鎵嶈兘婊¤凍“鏈灝忕殑”緇撴灉
鎼滅儲瀹屼箣鍚庣殑瀛楃涓叉瀯寤虹殑姝ラ鍥犱負StringBuffer鐢ㄧ殑涓嶇啛緇?br /> 鍙嶈岃皟璇曚簡寰堜箙
1 import java.util.*;
2 import java.util.regex.*;
3 import java.text.*;
4 import java.math.*;
5 import java.awt.geom.*;
6
7 public class IdealString
8 {
9 int[] table = new int[26];
10 int finalindex = 0;
11 int L;
12
13 public String construct(int length)
14 {
15 Arrays.fill(table, 0);
16 L = length;
17 if(dfs(1, 0, 0)){
18 StringBuffer sb = new StringBuffer();
19 char c = 'A';
20 int i , j = 0;
21 for(i = 0 ; i < L; ++ i)
22 sb.append(' ');
23 for(i = 0 ; i < finalindex; ++i){
24 sb.setCharAt(table[i] - 1, c ++);
25 table[i]--;
26 }
27 for(i = 0 ; i < L; ++ i){
28 if(sb.charAt(i) != ' ')
29 continue;
30 while(table[j] == 0) j++;
31 sb.setCharAt(i, (char)('A' + j));
32 table[j]--;
33 }
34 return sb.toString();
35 }
36 return new String();
37 }
38
39 boolean dfs(int num, int index, int sum){
40 table[index] = num;
41 int base = num + sum;
42 if(base == L){
43 table[index] = num;
44 finalindex = index + 1;
45 return true;
46 }
47 if(base > L)
48 return false;
49 int total = 0;
50 for(int i = 0 ; i <= index ; ++ i)
51 total += table[i];
52 for(int i = total + 1; i >= num + 1; -- i){
53 if(base + i <= L && dfs(i, index +1, base))
54 return true;
55 }
56 return false;
57 }
58 }
2 import java.util.regex.*;
3 import java.text.*;
4 import java.math.*;
5 import java.awt.geom.*;
6
7 public class IdealString
8 {
9 int[] table = new int[26];
10 int finalindex = 0;
11 int L;
12
13 public String construct(int length)
14 {
15 Arrays.fill(table, 0);
16 L = length;
17 if(dfs(1, 0, 0)){
18 StringBuffer sb = new StringBuffer();
19 char c = 'A';
20 int i , j = 0;
21 for(i = 0 ; i < L; ++ i)
22 sb.append(' ');
23 for(i = 0 ; i < finalindex; ++i){
24 sb.setCharAt(table[i] - 1, c ++);
25 table[i]--;
26 }
27 for(i = 0 ; i < L; ++ i){
28 if(sb.charAt(i) != ' ')
29 continue;
30 while(table[j] == 0) j++;
31 sb.setCharAt(i, (char)('A' + j));
32 table[j]--;
33 }
34 return sb.toString();
35 }
36 return new String();
37 }
38
39 boolean dfs(int num, int index, int sum){
40 table[index] = num;
41 int base = num + sum;
42 if(base == L){
43 table[index] = num;
44 finalindex = index + 1;
45 return true;
46 }
47 if(base > L)
48 return false;
49 int total = 0;
50 for(int i = 0 ; i <= index ; ++ i)
51 total += table[i];
52 for(int i = total + 1; i >= num + 1; -- i){
53 if(base + i <= L && dfs(i, index +1, base))
54 return true;
55 }
56 return false;
57 }
58 }
]]>
緇欏畾N鍜屼竴涓暣鏁伴泦鍚坅錛岀敤涓嶅睘浜巃鐨?涓暣鏁扮浉涔樺緱鍑虹N鏈榪戠殑鏁存暟
N鐨勮寖鍥?锝?000
浠庡皬鍒板ぇ3閲嶅驚鐜氨鍙互瑙?br /> 鐞嗚涓婄殑澶嶆潅搴﹂珮杈?000^3
濡傛灉紜疄綆椾竴嬈℃垜鐨勭數鑴戣璺戝埌6縐?br /> 涓嶈繃鍏跺疄褰撲箻縐噺鍘籒宸茬粡瓚呰繃涔嬪墠鐨勫樊棰濇椂灝卞彲浠reak浜?br /> 鎵浠ヨ綆楅噺鍏跺疄寰堝皬
鍔犱笂break綆椾竴嬈″彧瑕侀浂鐐歸浂鍑犵
鍙﹀鐨勯櫡闃辨槸寰幆濡傛灉鍙槸1锝?000鏄笉琛岀殑
鏈夊彲鑳戒細鐢ㄥ埌姣?000榪樺ぇ鐨勫洜瀛?br />
1
import java.util.*;
2import java.util.regex.*;
3import java.text.*;
4import java.math.*;
5import java.awt.geom.*;
6
7public class AvoidingProduct
8
{
9
int SIZE = 1101;
10
11 public int[] getTriple(int[] a, int n)
12
{
13 boolean[] table = new boolean[SIZE];
14 Arrays.fill(table, true);
15 for(int i = 0 ; i < a.length ; ++ i)
16 table[a[i]] = false;
17 int x,y,z;
18 int[] ans = new int[3];
19 Arrays.fill(ans, Integer.MAX_VALUE);
20 int gap = Integer.MAX_VALUE;
21 Outer:
22 for(x = 1 ; x < SIZE; ++ x){
23 if(table[x] == false) continue;
24 for(y = 1; y < SIZE; ++ y){
25 if(table[y] == false) continue;
26 for(z = 1 ; z < SIZE; ++ z){
27 if(table[z] == false) continue;
28 int total = x * y * z;
29 int sub = n - total;
30 if(Math.abs(sub) < gap){
31 ans[0] = x; ans[1] = y; ans[2] = z;
32 gap = Math.abs(sub);
33
}
34 if(sub < 0 && Math.abs(sub) >= gap)
35 break ;
36 }
37 }
38 }
39 return ans;
40 }
41
42
}
import java.util.*;2
import java.util.regex.*;3
import java.text.*;4
import java.math.*;5
import java.awt.geom.*;6
7
public class AvoidingProduct8
{
9
int SIZE = 1101;10
11
public int[] getTriple(int[] a, int n)12
{
13
boolean[] table = new boolean[SIZE];14
Arrays.fill(table, true);15
for(int i = 0 ; i < a.length ; ++ i)16
table[a[i]] = false;17
int x,y,z;18
int[] ans = new int[3];19
Arrays.fill(ans, Integer.MAX_VALUE);20
int gap = Integer.MAX_VALUE;21
Outer:22
for(x = 1 ; x < SIZE; ++ x){23
if(table[x] == false) continue;24
for(y = 1; y < SIZE; ++ y){25
if(table[y] == false) continue;26
for(z = 1 ; z < SIZE; ++ z){27
if(table[z] == false) continue;28
int total = x * y * z;29
int sub = n - total;30
if(Math.abs(sub) < gap){31
ans[0] = x; ans[1] = y; ans[2] = z;32
gap = Math.abs(sub);33
}34
if(sub < 0 && Math.abs(sub) >= gap)35
break ;36
}37
}38
}39
return ans;40
}41
42
}]]>
涓涓僵鐞冮泦鍚堬紝閲嶉噺鍚勪笉鐩稿悓錛岀粰瀹氬鍣ㄥぇ灝忓浣曞甫鍥炲敖閲忓鐨勫僵鐞?br />
闄愬埗鏉′歡涓僵鐞冧釜鏁板皬浜?3
鍥犳鐢―P鏉ヨ綆楀鏉傚害涓?^13*20*10鏄彲浠ユ帴鍙楃殑
榪欎竴棰樼敤memo鏂規硶鏇村姞鍚堥傚洜涓轟細鏈夊ぇ閲忕殑鏁版嵁涓嶉渶瑕佽綆?br /> 姣忎竴嬈￠兘榪唬璁＄畻鎵鏈夋湭濉殑鐞?br /> 鎶婄悆鏀捐繘鍙ｈ鎴栬呯洿鎺ュ紑濮嬪～涓嬩竴琚?br /> DP涓変釜鍙傛暟鏄痬ask錛屽墿浣欒鏁板拰鏈鍓╀綑絀洪棿
1import java.util.*;
2import java.util.regex.*;
3import java.text.*;
4import java.math.*;
5import java.awt.geom.*;
6
7public class CollectingMarbles
8{
9 int[][][] dic;
10 int L;
11 int[] mw;
12 int bagNumber;
13 int cap;
14
15 public int mostMarbles(int[] marblesWeights, int bagCapacity, int numberOfBags)
16 {
17 L = marblesWeights.length;
18 mw = marblesWeights;
19 bagNumber = numberOfBags;
20 cap = bagCapacity;
21 dic = new int[1<<L][bagNumber+1][cap+1];
22 for(int[][] a : dic)
23 for(int[] b : a)
24 Arrays.fill(b, -1);
25 int ans = recur(0, bagNumber, cap);
26 return ans == -1? 0 : ans;
27 }
28
29 private int recur(int mask, int bagNumber, int cur) {
30 // TODO Auto-generated method stub
31 if(bagNumber == 0)
32 return 0;
33 if(dic[mask][bagNumber][cur] > -1)
34 return dic[mask][bagNumber][cur];
35 dic[mask][bagNumber][cur] = 0;
36 for(int i = 0 ; i < L ; ++ i){
37 if((mask & (1 << i)) == 0 && mw[i] <= cur){
38 dic[mask][bagNumber][cur] = Math.max(dic[mask][bagNumber][cur],
39 1+recur(mask|1<<i, bagNumber, cur-mw[i]));
40
41 }
42 dic[mask][bagNumber][cur] = Math.max(dic[mask][bagNumber][cur],
43 recur(mask, bagNumber-1, cap));
44 }
45
46 return dic[mask][bagNumber][cur];
47 }
48}
import java.util.*;2
import java.util.regex.*;3
import java.text.*;4
import java.math.*;5
import java.awt.geom.*;6
7
public class CollectingMarbles8
{9
int[][][] dic;10
int L;11
int[] mw;12
int bagNumber;13
int cap;14
15
public int mostMarbles(int[] marblesWeights, int bagCapacity, int numberOfBags)16
{17
L = marblesWeights.length;18
mw = marblesWeights;19
bagNumber = numberOfBags;20
cap = bagCapacity;21
dic = new int[1<<L][bagNumber+1][cap+1];22
for(int[][] a : dic)23
for(int[] b : a)24
Arrays.fill(b, -1);25
int ans = recur(0, bagNumber, cap);26
return ans == -1? 0 : ans;27
}28
29
private int recur(int mask, int bagNumber, int cur) {30
// TODO Auto-generated method stub31
if(bagNumber == 0)32
return 0;33
if(dic[mask][bagNumber][cur] > -1)34
return dic[mask][bagNumber][cur];35
dic[mask][bagNumber][cur] = 0;36
for(int i = 0 ; i < L ; ++ i){37
if((mask & (1 << i)) == 0 && mw[i] <= cur){38
dic[mask][bagNumber][cur] = Math.max(dic[mask][bagNumber][cur],39
1+recur(mask|1<<i, bagNumber, cur-mw[i]));40
41
}42
dic[mask][bagNumber][cur] = Math.max(dic[mask][bagNumber][cur], 43
recur(mask, bagNumber-1, cap));44
}45
46
return dic[mask][bagNumber][cur];47
}48
}]]>
涓緇勫瓧絎︿覆錛屽浣曞皢鍏朵腑涓閮ㄥ垎鍙崇Щ鑻ュ共鏍鹼紝浣垮緱鏌愪竴鍒楃殑綰靛悜鎭板ソ涓鴻姹傜殑瀛楃涓詫紝騫朵笖緇欏嚭縐誨姩鏈灝戠殑絳旀銆?br />
榪欎竴棰樹箥涓鐪嬭寰楀緢澶嶆潅
鏈夌偣鍍忎箣鍓嶅仛榪囩殑鍚変粬鐞村雞鐨勯偅涓棰?br /> 鍙槸榪欎釜澶嶆潅搴?^50鏄悆涓嶆秷鐨?br /> 浣嗘槸榪欓噷鏈変袱鐐逛笉鍚?br /> 涓涓槸榪欓噷鍙兘鍙崇Щ
鍙︿竴涓緢閲嶈鐨勬槸榪欎釜鏌愪竴鍒楀皢鎴愪負涓涓湁鍙傝冩剰涔夌殑鍧愭爣
鍗崇敤榪欎釜鍒楀彿鏉ラ亶鍘?鐪嬬瓟妗堝湪鍝竴鍒楄В絳旀渶灝?br /> 鎯抽氳繖涓鐐?鍚庨潰灝卞緢瀹規槗浜?br />
1import java.util.*;
2import java.util.regex.*;
3import java.text.*;
4import java.math.*;
5import java.awt.geom.*;
6
7public class MatchString
8{
9 public int placeWords(String matchString, String[] matchWords)
10 {
11 List<ArrayList<Integer> > occur = new ArrayList<ArrayList<Integer> >();
12 int L = matchWords.length;
13 int end = 0;
14 int start = Integer.MAX_VALUE;
15 int i,j;
16 for(i = 0 ; i < L ; ++ i){
17 ArrayList<Integer> temp = new ArrayList<Integer>();
18 char c = matchString.charAt(i);
19 for(j = 0 ; j < matchWords[i].length(); ++ j){
20 if(matchWords[i].charAt(j) == c)
21 temp.add(j);
22 }
23 if(temp.isEmpty()) return -1;
24 occur.add(temp);
25 if(matchWords[i].length() > end)
26 end = matchWords[i].length();
27 if(temp.get(0) < start)
28 start = temp.get(0);
29 }
30 int ans = Integer.MAX_VALUE;
31 Outer:
32 for(i = start; i <= end; ++ i){
33 int tempans = 0;
34 for(int k = 0 ; k < L; ++ k){
35 j = 0;
36 while(j < occur.get(k).size() && occur.get(k).get(j) <= i)
37 ++j;
38 if(j == 0)
39 continue Outer;
40 tempans += i - occur.get(k).get(j-1);
41 }
42 ans = Math.min(ans, tempans);
43 }
44 return ans;
45 }
46}
import java.util.*;2
import java.util.regex.*;3
import java.text.*;4
import java.math.*;5
import java.awt.geom.*;6
7
public class MatchString8
{9
public int placeWords(String matchString, String[] matchWords)10
{11
List<ArrayList<Integer> > occur = new ArrayList<ArrayList<Integer> >();12
int L = matchWords.length;13
int end = 0;14
int start = Integer.MAX_VALUE;15
int i,j;16
for(i = 0 ; i < L ; ++ i){17
ArrayList<Integer> temp = new ArrayList<Integer>();18
char c = matchString.charAt(i);19
for(j = 0 ; j < matchWords[i].length(); ++ j){20
if(matchWords[i].charAt(j) == c)21
temp.add(j);22
}23
if(temp.isEmpty()) return -1;24
occur.add(temp);25
if(matchWords[i].length() > end)26
end = matchWords[i].length();27
if(temp.get(0) < start)28
start = temp.get(0);29
}30
int ans = Integer.MAX_VALUE;31
Outer:32
for(i = start; i <= end; ++ i){33
int tempans = 0;34
for(int k = 0 ; k < L; ++ k){35
j = 0;36
while(j < occur.get(k).size() && occur.get(k).get(j) <= i)37
++j;38
if(j == 0)39
continue Outer;40
tempans += i - occur.get(k).get(j-1); 41
}42
ans = Math.min(ans, tempans);43
}44
return ans;45
}46
}]]>
緇欏畾涓涓瓧絎︿覆閲岄潰鍖呭惈浜嗚嫢騫蹭釜1锝?鐨勬暟瀛楋紝鍙︿竴涓瓧絎︿覆涓哄叾瀛愰泦錛屽浜庡悗鑰呬腑姣忎釜瀛楃錛屼粠鍓嶉潰瀛楃涓蹭腑鍒犲幓鐩稿簲鐨勪竴涓暟瀛?br /> 姹傚垹鍘誨墿涓嬬殑鏁板瓧鐨勬渶澶у?br />
鐢變簬鏄眰鏈澶у鹼紝鐩存帴鍦ㄨ綆楄繃紼嬩腑涓嶆柇璐績鍦ㄦ渶楂樹綅璋嬪彇鏈澶у?br /> 浠庡墠闈㈡寜鐓?锝?鐨勯『搴忓姹傚彲浠ュ仛褰撳墠鏈楂樹綅鐨勬渶澶у?br /> 鍒嗕互涓?姝ワ細
1.瀵逛簬鎵鏈夐兘瑕佸垹鍘葷殑鏁板瓧錛岀洿鎺ュ垹鍏?br /> 2.浠庡墠闈㈠紑濮嬫煡鎵撅紝灝嗘墍鏈夋棤娉曞垹鍘葷殑鏁板瓧鍔犲叆絳旀涓?br /> 3.浠庡墠闈㈡寜鐓?锝?鐨勯『搴忔壘鍙互鐢ㄧ殑鏈澶у鹼紝濡傛灉鍏跺墠闈㈢殑鎵鏈夋暟瀛楅兘鍙互鍒犲幓錛岄偅涔堝氨鍙栬繖涓暟錛屽惁鍒欓掑噺
4.鑻ュ瓧絎︿覆涓虹┖鍒欑粨鏉燂紝鍚﹀垯寰幆絎竴姝?br />
榪欎竴棰樿凍瓚沖仛浜?涓灝忔椂
鎯蟲硶寰堝揩灝辨湁浜?br /> 浣嗘槸鍦ㄥ疄鐜頒腑String綾誨瀷涓嶈兘淇敼鍜屽垹闄ょ殑闂寰堥毦澶勭悊
鏈鍚庡共鑴嗘妸String杞寲涓篖inkedList鏉ュ仛
涓嶈繃娌℃湁鐪嬬瓟妗堣В鍐蟲帀寰堥毦寰?..緇х畫鍔犳補
1import java.util.*;
2import java.util.regex.*;
3import java.text.*;
4import java.math.*;
5import java.awt.geom.*;
6
7public class RemovingDigits
8{
9 public String maxNumber(String number, String digits)
10 {
11 int[] numCnt = new int[10];
12 int[] digCnt = new int[10];
13 Arrays.fill(numCnt, 0);
14 Arrays.fill(digCnt, 0);
15 int i;
16 for(i = 0 ; i < number.length(); ++ i)
17 numCnt[number.charAt(i)-'0']++;
18 for(i = 0 ; i < digits.length(); ++ i)
19 digCnt[digits.charAt(i) - '0']++;
20 StringBuilder ans = new StringBuilder("");
21 List<Character> target = new LinkedList<Character>();
22 for(i = 0 ; i < number.length(); ++ i){
23 target.add(number.charAt(i));
24 }
25 while(!target.isEmpty()){
26 //remove digits that all should be removed
27 for(i = 1 ; i < 10 ; ++ i){
28 if(numCnt[i] == digCnt[i]){
29 char c = (char) ('0'+i);
30 while(target.remove((Character)c));
31// target.remove((Character)c);
32 numCnt[i] = 0;
33 digCnt[i] = 0;
34 }
35 }
36 //append all that cannot be removed
37 for(i = 0 ; i < target.size(); ++ i){
38 if(digCnt[target.get(i)-'0'] != 0)
39 break;
40 ans.append(target.get(i));
41 }
42 for(--i;i >= 0; -- i){
43 numCnt[target.get(i)-'0']--;
44 target.remove(i);
45 }
46 if(target.isEmpty())
47 break;
48
49 //find the largest head number
50 Outer:
51 for(i = 9 ; i > 0 ; -- i){
52 //whether there is still this number
53 if(numCnt[i] == 0)
54 continue;
55 char c = (char) ('0'+i);
56 int idx = target.indexOf((Character)c);
57 int j;
58 int[] tempCnt = new int[10];
59 Arrays.fill(tempCnt, 0);
60 for(j = 0 ; j < idx ; ++ j)
61 tempCnt[target.get(j)-'0']++;
62 for(j = 1 ; j < 10; ++ j){
63 if(tempCnt[j] > digCnt[j])
64 continue Outer;
65 }
66 for(j = 1; j < 10; ++ j){
67 digCnt[j] -= tempCnt[j];
68 numCnt[j] -= tempCnt[j];
69 }
70 numCnt[i]--;
71 ans.append(target.get(idx));
72 for(j = idx; j >=0; --j)
73 target.remove(j);
74 break;
75
76 }
77 }
78 return ans.toString();
79 }
80}
import java.util.*;2
import java.util.regex.*;3
import java.text.*;4
import java.math.*;5
import java.awt.geom.*;6
7
public class RemovingDigits8
{9
public String maxNumber(String number, String digits)10
{11
int[] numCnt = new int[10];12
int[] digCnt = new int[10];13
Arrays.fill(numCnt, 0);14
Arrays.fill(digCnt, 0);15
int i;16
for(i = 0 ; i < number.length(); ++ i)17
numCnt[number.charAt(i)-'0']++;18
for(i = 0 ; i < digits.length(); ++ i)19
digCnt[digits.charAt(i) - '0']++;20
StringBuilder ans = new StringBuilder("");21
List<Character> target = new LinkedList<Character>();22
for(i = 0 ; i < number.length(); ++ i){23
target.add(number.charAt(i));24
}25
while(!target.isEmpty()){26
//remove digits that all should be removed27
for(i = 1 ; i < 10 ; ++ i){28
if(numCnt[i] == digCnt[i]){29
char c = (char) ('0'+i);30
while(target.remove((Character)c));31
// target.remove((Character)c);32
numCnt[i] = 0;33
digCnt[i] = 0;34
}35
}36
//append all that cannot be removed37
for(i = 0 ; i < target.size(); ++ i){38
if(digCnt[target.get(i)-'0'] != 0)39
break;40
ans.append(target.get(i)); 41
}42
for(--i;i >= 0; -- i){43
numCnt[target.get(i)-'0']--;44
target.remove(i);45
}46
if(target.isEmpty())47
break;48
49
//find the largest head number50
Outer:51
for(i = 9 ; i > 0 ; -- i){52
//whether there is still this number53
if(numCnt[i] == 0)54
continue;55
char c = (char) ('0'+i);56
int idx = target.indexOf((Character)c);57
int j;58
int[] tempCnt = new int[10];59
Arrays.fill(tempCnt, 0);60
for(j = 0 ; j < idx ; ++ j)61
tempCnt[target.get(j)-'0']++;62
for(j = 1 ; j < 10; ++ j){63
if(tempCnt[j] > digCnt[j])64
continue Outer;65
}66
for(j = 1; j < 10; ++ j){67
digCnt[j] -= tempCnt[j];68
numCnt[j] -= tempCnt[j];69
}70
numCnt[i]--;71
ans.append(target.get(idx));72
for(j = idx; j >=0; --j)73
target.remove(j);74
break;75
76
}77
}78
return ans.toString();79
}80
}]]>
鏍囧噯鐨凞P棰樼洰
鍦ㄨ繍綆椾腑鍑犲蹇界暐浜嗘瘮杈冩鏌ワ紝鐗規畩鍊?br /> 瀵艱嚧閿欒浜嗕袱嬈?br /> 鍋氶鐩湪涓昏鎬濊礬鏈変簡涔嬪悗榪樻槸瑕佷粩緇嗚冭檻鐗規畩鎯呭喌
寰寰浜哄鍏蟲敞鐨勫湴鏂瑰氨鍦ㄨ繖閲?br />
1import java.util.*;
2import java.util.regex.*;
3import java.text.*;
4import java.math.*;
5import java.awt.geom.*;
6
7public class TriviaGame
8{
9 public int maximumScore(int[] points, int tokensNeeded, int[] bonuses)
10 {
11 int L = points.length;
12 int[][] dic = new int[L][tokensNeeded+1];
13 for(int[] i:dic)
14 Arrays.fill(i, -100000);
15 int i;
16 dic[0][0] = -1 * points[0];
17 dic[0][1] = points[0];
18 if(tokensNeeded == 1)
19 dic[0][0] = dic[0][1]+bonuses[0];
20 for(i = 1; i < L; ++ i){
21 if(dic[i-1][0] - points[i] > dic[i][0])
22 dic[i][0] = dic[i-1][0] - points[i];
23 int j;
24 for(j = 1; j < Math.min(i+2, tokensNeeded); ++ j){
25 int a = dic[i-1][j-1] + points[i];
26 int b = dic[i-1][j] - points[i];
27 dic[i][j] = Math.max(a, b);
28 }
29 if(j == tokensNeeded){
30 dic[i][j] = dic[i-1][j-1] + points[i];
31 dic[i][j] += bonuses[i];
32 if(i != L - 1 && dic[i][j] > dic[i][0])
33 dic[i][0] = dic[i][j];
34 }
35
36 }
37 int max = dic[L-1][0];
38 for(int in:dic[L-1])
39 if(in > max)
40 max = in;
41 return max;
42 }
43}
import java.util.*;2
import java.util.regex.*;3
import java.text.*;4
import java.math.*;5
import java.awt.geom.*;6
7
public class TriviaGame8
{9
public int maximumScore(int[] points, int tokensNeeded, int[] bonuses)10
{11
int L = points.length;12
int[][] dic = new int[L][tokensNeeded+1];13
for(int[] i:dic)14
Arrays.fill(i, -100000);15
int i;16
dic[0][0] = -1 * points[0];17
dic[0][1] = points[0];18
if(tokensNeeded == 1)19
dic[0][0] = dic[0][1]+bonuses[0];20
for(i = 1; i < L; ++ i){21
if(dic[i-1][0] - points[i] > dic[i][0])22
dic[i][0] = dic[i-1][0] - points[i];23
int j;24
for(j = 1; j < Math.min(i+2, tokensNeeded); ++ j){25
int a = dic[i-1][j-1] + points[i];26
int b = dic[i-1][j] - points[i];27
dic[i][j] = Math.max(a, b); 28
}29
if(j == tokensNeeded){30
dic[i][j] = dic[i-1][j-1] + points[i];31
dic[i][j] += bonuses[i];32
if(i != L - 1 && dic[i][j] > dic[i][0])33
dic[i][0] = dic[i][j];34
}35
36
}37
int max = dic[L-1][0];38
for(int in:dic[L-1])39
if(in > max)40
max = in;41
return max;42
}43
}]]>
http://www.topcoder.com/stat?c=problem_statement&pm=8547&rd=11128
姹俛鍒癮+b鎵鏈夌殑鏁扮殑cool divider鏁伴噺涔嬪拰錛屽嵆鏈韓鑳借鏁撮櫎浣嗘槸鍏秐嬈℃柟涓嶈兘琚暣闄?br />
鐢變簬鏁版嵁楂樿揪10^7錛屾毚鍔涙病鏈夊彲鑳斤紝灝嗕箻娉曡漿鍖栦負鍔犳硶涔熶粛鐒惰綆楅噺澶ぇ
絳旀緇欏嚭浜嗗緢濂界殑瑙ｅ喅鏂規硶
瀵逛簬a鍒癮+b涓棿鐨勬暟錛屽彲浠ユ暣闄鐨勪釜鏁頒負(a+b)/i - (a-1)/i錛屼互涓婂潎涓篿nt鐨勯櫎娉曟搷浣?br /> 榪欐牱澶уぇ鑺傜渷浜嗚綆楅噺
鍞竴瑕佹敞鎰忕殑鏄鏋渂澶т簬a錛屼細灝嗕竴閮ㄥ垎鍊兼湰韜璁＄畻涓嬈?br /> 鍥犳鏈鍚庤鍋氫竴鐐逛慨鏁?/p>
1import java.util.*;
2import java.util.regex.*;
3import java.text.*;
4import java.math.*;
5import java.awt.geom.*;
6
7public class ProperDivisors
8{
9 public int analyzeInterval(int a, int b, int n)
10 {
11 int i,sum = 0;
12 for(i = 2 ; i <= (a+b)/2; ++ i)
13 sum += (a+b)/i - (a-1)/i;
14 for(i = 2 ; i <= (a+b)/2; ++ i){
15 int k = pow(i,n);
16 sum -= (a+b)/k - (a-1)/k;
17 }
18 if(b >= a){
19 sum -= (a+b)/2 - a + 1;
20 if(a == 1) sum++;
21 }
22
23 return sum;
24 }
25
26 public int pow(int k, int n){
27 int i;
28 long result = k;
29 for( i = 1 ; i < n; ++ i){
30 result *= k;
31 if(result > Integer.MAX_VALUE)
32 return Integer.MAX_VALUE;
33 }
34 int res = (int)result;
35 return res;
36 }
37}
import java.util.*;2
import java.util.regex.*;3
import java.text.*;4
import java.math.*;5
import java.awt.geom.*;6
7
public class ProperDivisors8
{9
public int analyzeInterval(int a, int b, int n)10
{11
int i,sum = 0;12
for(i = 2 ; i <= (a+b)/2; ++ i)13
sum += (a+b)/i - (a-1)/i;14
for(i = 2 ; i <= (a+b)/2; ++ i){15
int k = pow(i,n);16
sum -= (a+b)/k - (a-1)/k;17
}18
if(b >= a){19
sum -= (a+b)/2 - a + 1;20
if(a == 1) sum++;21
}22
23
return sum;24
}25
26
public int pow(int k, int n){27
int i;28
long result = k;29
for( i = 1 ; i < n; ++ i){30
result *= k;31
if(result > Integer.MAX_VALUE)32
return Integer.MAX_VALUE;33
}34
int res = (int)result;35
return res;36
}37
}]]>
http://www.topcoder.com/stat?c=problem_statement&pm=8307&rd=11124
涓緇凱attern錛屾瘡涓綅涓婃槸瀛楁瘝鎴栬呴氶厤絎?#8220;錛?#8221;錛屾眰鎭板ソ絎﹀悎K涓狿attern鐨勫瓧絎︿覆鏁?br />
榪欎釜棰樼洰楹葷儲鍦ㄦ伆濂斤紙exactly錛変笂
鍚﹀垯瀹屽叏鍙互鏆村姏澶勭悊
榪欓噷瑕佹伆濂斤紝鍗崇鍚圞涓屼笉絎﹀悎K錛?涓?br /> 鐢―P閫愪釜浣嶇疆澶勭悊
璁＄畻鍑烘瘡涓瓧姣嶅尮閰嶇殑Pattern闆嗗悎錛屽啀鍜屽墠闈㈢殑Pattern闆嗗悎鍙栦氦闆嗚綆楄繖涓琛岀殑緇撴灉
璁＄畻榪囩▼涓彇浜ら泦鐨?#8220;&”閿欏啓鎴愪簡“|” 澶敓鐤忎簡
1import java.util.*;
2import java.util.regex.*;
3import java.text.*;
4import java.math.*;
5import java.awt.geom.*;
6
7public class SetOfPatterns
8{
9 public int howMany(String[] patterns, int k)
10 {
11 int[][] tab = new int[50][1<<15];
12 int L = patterns.length;
13 int T = 1 << L;
14
15 for(int[] i:tab)
16 Arrays.fill(i, 0);
17 int i,j;
18 char c;
19 for(i = 0 ; i < patterns[0].length(); ++ i){
20
21 for(c = 'a'; c <= 'z'; ++ c){
22 int mask = 0 ;
23 for(j = 0 ; j < L ; ++ j){
24 if(patterns[j].charAt(i) == c || patterns[j].charAt(i) =='?')
25 mask |= 1 << j;
26 }
27 if(i == 0){
28 tab[i][mask]++;
29 }
30 else{
31 for(j = 0 ; j < (T); ++ j){
32 int fin = j & mask;
33 tab[i][fin] = (tab[i][fin] + tab[i-1][j])%1000003;
34 }
35 }
36 }
37 }
38 int ans=0;
39 for(i = 0 ; i < T; ++ i){
40 int cnt = 0;
41 for(j = 0 ; j < L; ++ j){
42 int temp = i & (1 << j);
43 if(temp != 0)
44 cnt ++;
45 }
46 if(cnt == k)
47 ans = (ans + tab[patterns[0].length()-1][i]) % 1000003;
48 }
49 return ans;
50 }
51}
import java.util.*;2
import java.util.regex.*;3
import java.text.*;4
import java.math.*;5
import java.awt.geom.*;6
7
public class SetOfPatterns8
{9
public int howMany(String[] patterns, int k)10
{11
int[][] tab = new int[50][1<<15];12
int L = patterns.length;13
int T = 1 << L;14
15
for(int[] i:tab)16
Arrays.fill(i, 0);17
int i,j;18
char c;19
for(i = 0 ; i < patterns[0].length(); ++ i){20
21
for(c = 'a'; c <= 'z'; ++ c){22
int mask = 0 ;23
for(j = 0 ; j < L ; ++ j){24
if(patterns[j].charAt(i) == c || patterns[j].charAt(i) =='?')25
mask |= 1 << j;26
}27
if(i == 0){28
tab[i][mask]++;29
}30
else{31
for(j = 0 ; j < (T); ++ j){32
int fin = j & mask;33
tab[i][fin] = (tab[i][fin] + tab[i-1][j])%1000003;34
}35
}36
}37
}38
int ans=0;39
for(i = 0 ; i < T; ++ i){40
int cnt = 0;41
for(j = 0 ; j < L; ++ j){42
int temp = i & (1 << j);43
if(temp != 0)44
cnt ++;45
}46
if(cnt == k)47
ans = (ans + tab[patterns[0].length()-1][i]) % 1000003;48
}49
return ans;50
}51
}]]>
]]>