今天好不容易在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
西月弦 阅读(357)
评论(0) 编辑 收藏 引用 所属分类:
解题报告