今天好不容易在gentoo下配置好了java和javaws...(用的itedtea) 終于可以做tc了，之前由于做系統(tǒng)＋講課好久沒有更新blog了，最近也沒有好好刷題，罪過...
250pt
一個(gè)點(diǎn)數(shù)為50的無向圖，每個(gè)節(jié)點(diǎn)i有一個(gè)分值v[i]，當(dāng)你進(jìn)入到v[i]的時(shí)候，你的分?jǐn)?shù)是value(當(dāng)前分?jǐn)?shù)) XOR v[i]，請(qǐng)問從點(diǎn)0開始，你任意走能獲得的最大分?jǐn)?shù)。
算法分析：
二維狀態(tài)，廣搜即可...
srm 556div1 250pt
1 #include<queue>
2 #include<vector>
3 #include<string>
4 #include<iostream>
5 using namespace std;
6 const int M = 1200;
7 bool dp[55][M];
8 class XorTravelingSalesman{
9 public:
10 int maxProfit(vector<int>val,vector<string>G){
11 int n = G.size();
12 queue<pair<int,int> >Q;
13 dp[0][val[0]] = 1;
14 Q.push(make_pair(0,val[0]));
15 while(!Q.empty()){
16 int u=Q.front().first;
17 int p=Q.front().second,q;
18 Q.pop();
19 for(int v=0;v<n;v++) if(G[u][v]=='Y'&&!dp[v][q=p^val[v]]){
20 dp[v][q]=1;
21 Q.push(make_pair(v,q));
22 }
23 }
24 for(int i = M-1; i>=0; i--) for(int j = 0; j < n; j++) if(dp[j][i]) return i;
25 }};500pt
你手頭上有一個(gè)數(shù)A,通過這個(gè)數(shù)A你要構(gòu)造一個(gè)大于B的數(shù)C，規(guī)則如下。
每次你講數(shù)A的最左端的數(shù)拿走，放到C的最左端或者最右端。
求你能構(gòu)造出的最小的C。
算法分析：
動(dòng)態(tài)規(guī)劃，dp[i][l][r]表示A的前i個(gè)數(shù)去構(gòu)造比B[l]...B[r]大的數(shù)的最小的數(shù)。因?yàn)榍癷個(gè)數(shù)構(gòu)造的總是B的連續(xù)一段...
所以第i個(gè)數(shù)要么放在l位置，要么放在r位置嘍~
srm 556div1 500pt
1 #include<string>
2 #include<iostream>
3 using namespace std;
4 string dp[55][55][55][2],a,b,as[55];
5 string dfs(int n){
6 if(as[n]!="!!")return as[n];
7 if(n==0) return as[n]=a[0];
8 string ta, tb;
9 ta=tb=a[n];
10 ta = dfs(n-1)+ta;
11 tb = tb+dfs(n-1);
12 return as[n]=min(ta,tb);
13 }
14 string work(int n,int l,int r,int c){
15 char x = a[n];
16 string &ans = dp[n][l][r][c];
17 if(ans != "!!") return ans;
18 if(n==0){if(c&&a[n]>b[l]) return ans = x; if(!c&&x>=b[l]) return ans = x; return ans =""; }
19 string ta,tb;tb=x;
20 int t = c;
21 if(x<b[r]) t = 1; else if(x > b[r]) t =0;
22 ta = work(n-1,l,r-1,t);
23 ta.push_back(x);
24 if(x == b[l])
25 tb = tb + work(n-1,l+1,r,c);
26 else if(x > b[l])
27 tb = tb + dfs(n-1);
28 if(ta .size()==1) ta="";
29 if(tb .size()==1) tb="";
30
31 // cout<<n<<" "<<l<<" "<<r<<" ta: "<<ta<<" tb: "<<tb<<endl;
32 if(ta=="") return ans=tb; if(tb=="")return ans=ta;
33 return ans = min(ta,tb);
34 }
35 class LeftRightDigitsGame2{
36 public:
37 string minNumber(string digits, string lowerBound){
38 a = digits; b = lowerBound;int N=55;
39 for(int i =0;i<N;i++)for(int j=0;j<N;j++) for(int k=0;k<N;k++) dp[i][j][k][0]=dp[i][j][k][1]="!!";
40 for(int i=0;i<N;i++) as[i]="!!";
41 return work(a.size()-1,0,a.size()-1,0);
42 }
43 };
posted on 2012-10-01 22:09
西月弦 閱讀(377)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
解題報(bào)告