今天好不容易在gentoo下配置好了java和javaws...(用的itedtea) 終于可以做tc了，之前由于做系統＋講課好久沒有更新blog了，最近也沒有好好刷題，罪過...
250pt
一個點數為50的無向圖，每個節點i有一個分值v[i]，當你進入到v[i]的時候，你的分數是value(當前分數) XOR v[i]，請問從點0開始，你任意走能獲得的最大分數。
算法分析：
二維狀態，廣搜即可...
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
你手頭上有一個數A,通過這個數A你要構造一個大于B的數C，規則如下。
每次你講數A的最左端的數拿走，放到C的最左端或者最右端。
求你能構造出的最小的C。
算法分析：
動態規劃，dp[i][l][r]表示A的前i個數去構造比B[l]...B[r]大的數的最小的數。因為前i個數構造的總是B的連續一段...
所以第i個數要么放在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
西月弦 閱讀(400)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告