繼續是misof 數字教學里面的習題~ 第一篇的最后一道題了~

Problem Statement

You are in a maze containing revolving doors. The doors can be turned 90 degrees by pushing against them in either direction. You are to find a route from the start square to the end square that involves revolving as few doors as possible. Given a map of the maze, determine the fewest number of door revolutions necessary to get from the start to the end.

In the map:

   ' ': empty space
   '#': wall
   'O': center of a revolving door (letter "oh", not zero)
   '-': horizontal door (always adjacent to a 'O')
   '|': vertical door (always adjacent to a 'O')
   'S': start square
   'E': end square

Each revolving door will always be oriented horizontally (with two horizontal segments) or vertically (with two vertical segments):

    |
    O  or  -O-
    |

Doors can be revolved 90 degrees by moving onto a door segment from any of the 4 squares diagonally adjacent to the door center, i.e., the 'X' characters below:

   X|X     X X
    O  or  -O-
   X|X     X X

Here is an example map:

        ###
        #E#
       ## #
    ####  ##
    # S -O-#
    # ###  #
    #      #
    ########

In this example, 2 door revolutions are necessary to get from 'S' to 'E'. The first turn is shown here:

        ###         ###
        #E#         #E#
       ## #        ## #
    ####  ##    #### |##
    # S -O-#    # S  OX#
    # ### X#    # ###| #
    #      #    #      #
    ########    ########

And the second turn is shown here:

        ###         ###
        #E#         #E#
       ## #        ## #
    ####X|##    #### X##
    # S  O #    # S -O-#
    # ###| #    # ###  #
    #      #    #      #
    ########    ########

Your method should return an int, the minimum number of door revolutions necessary to get from the start square to the end square. If there is no way to reach the end square, return -1.

Definition

Class:
RevolvingDoors

Method:
turns

Parameters:
vector <string>

Returns:
int

Method signature:
int turns(vector <string> map)

(be sure your method is public)

Notes

-
Assume that all squares off the edge of the map are walls.

Constraints

-
map will contain between 3 and 50 elements, inclusive.

-
Each element of map will contain between 3 and 50 characters, inclusive.

-
Each element of map will contain the same number of characters.

-
Each character in map will be one of 'S', 'E', 'O', '-', '|', '#', and ' ' (space).

-
There will be exactly one 'S' and one 'E' in map.

-
There will be between 1 and 10 doors, inclusive, and they will be formatted in map as described in the problem statement.

-
No two doors will be close enough for any part of them to occupy the same square.

-
It is not allowed for a door to be blocked and unable to turn. There will not be any walls in any of the 4 squares immediately adjacent to the center of a door, nor will a door be on the edge of the map.

關鍵是門的狀態表示，參考了網站上的代碼，挑了一個比較簡練的，用的優先級隊列。寫完調好發現TLE 囧~ copy出網站上的再run依然TLE``` ``` 看了下發現現在的system testing 比原來增加了幾個測試用例~~~   于是找出misof大牛的解法，發現對狀態處理一樣的~~~只不過用了memo和deque，省去了優先級隊列調整的時間開銷，改好了就pass了~ 上代碼~~：

中文copy是亂碼···囧啊~~ 俺的破爛英文注釋啊~~~

Problem Statement

Just before a chess match between two teams, each team's coach secretly determines an ordering of his team's players. The first players in each team then get to play against each other, the second players in each team play against each other, etc. The team with the most wins will win the match.

You are the coach for one of the teams, and you have somehow managed to find out the order of the players in the other team. Based on that, you want to order your players so that your team's expected score is maximized to your advantage. The expected score of a single game can be calculated by the following formula (which is directly derived from how the international chess rating system works):

EA = 1 / (1 + 10 (RB - RA)/400)

EB = 1 / (1 + 10 (RA - RB)/400)

where R_A and R_B are the ratings of player A and B, and E_A and E_B are the expected scores for each player. For instance, if R_A is 2432 and R_B is 2611, the expected score for player A is 1 / (1 + 10^179/400) = 0.263005239459. The expected score for a team is the sum of the expected scores for the players in that team.

To make things a bit more complicated, the players in a team must be ordered such that a player with rating x plays before all players with rating strictly less than x - lim, where lim is a given non-negative integer. For example, if lim is 100, a player with rating 2437 must play before a player with rating 2336 but not necessarily before a player with rating 2337.

Create a class ChessMatch containing the method bestExpectedScore which takes a vector <int> teamA, the ratings of your players (in no particular order); a vector <int> teamB, the ratings of your opponent's players in the order they will play; and an int lim, the limit determining how freely you can order your players. You can assume that your opponent's players will be ordered in accordance with lim. The method should return a double, your team's expected score if you order your players optimally.

Definition

Class:
ChessMatch

Method:
bestExpectedScore

Parameters:
vector <int>, vector <int>, int

Returns:
double

Method signature:
double bestExpectedScore(vector <int> teamA, vector <int> teamB, int lim)

(be sure your method is public)

要求最好的得分，要遍歷所有的排列方式顯然不可能。如果轉化問題為依次放置每個選手到每一個位置，那么只要求出剩下選手排列中使得得分最大的就可以了，可以想到dp方法的最有子問題定義。

用每一位記錄當前的選手分配情況，如果為0，則已經分配，如果為1，則還未分配。pos來記錄當前要分配的位置。對于每一個子集，考慮每一個為1的也就是未分配的選手使位于pos位置，然后check 是否滿足在他之后的球員（也就是剩下的是1的位）是否滿足條件的不等式，滿足則更新當前分配的最優成績。最終 2^N-1 的成績即為所求。

上面的方法使用遞歸，下面是使用遞推的程序。即從子集出發最終到達2^n-1的思路。在這里把A隊伍先從大到小排序。在每一個子集記錄每一個未分配選手的得分和要分配的位置。

程序中思路為：依次從子集中選取一個選手作為第bits-1個選手，也就是說子集中剩下的元素要放在這個選手前面，由于選手從小到大遍歷，只需要遍歷到s[j]<=s[bits-1]+lim 為止，也就說滿足這個子集中最小的選手+lim >=選中的 即可，然后更新當前子集的得分

注釋中思路為: 依次從子集選取一個選手作為當前子集中的第一個元素，也就是整體的第n-bits個元素，這次從大到小遍歷，這樣只需要保證，位于子集第一個的元素+lim>=子集中最大的元素(s[0])，即可，然后更新當前子集得分

最終全集2^n-1的即為所求

roblem Statement

Character j in element i (both 0-based) of messages denotes how many messages employee i sent to employee j. You will return a vector <int> containing the hierarchy of the employees within the company. Element 0 is the highest ranked employee, and so forth. The returned ranking should minimize the number of messages sent from lower ranked employees to higher ranked employees. If multiple solutions are possible, return the one with element 0 minimal. If there are still ties, minimize element 1, etc.

Definition

Class:
CompanyMessages

Method:
getRank

Parameters:
vector <string>

Returns:
vector <int>

Method signature:
vector <int> getRank(vector <string> messages)

(be sure your method is public)

Constraints

-
messages will contain between 2 and 15 elements inclusive.

-
Each element of messages will contain exactly N characters, where N is the number of elements in messages.

-
Each character in messages will be a digit ('0'-'9').

-
Character i in element i of messages will be '0'.

按照題目說明可知，按照找到的順序，所有從低級向高級發的信得數目和應該是最小的。又觀察到，只要確定了第一個，也就是級別最高的boss，那么剩下的員工怎么排列，他們向最高boss 發信數是不變的，從而子問題就是在剩下員工中找到 低級向高級發信數最小的排列 ，顯然這符合DP問題最優子結構的問題。

T[1···N]=Min{sum(N <->{1-N-1},T[1-N-1] } 得到狀態方程后很容易寫出程序 ，可以使用備忘錄dp

Code Snippet

#define REP(i, n) for (int i = 0; i < (n); ++i)

#define two(X) (1<<(X))
#define contain(S,X) ((S&two(X))>0)

int A[1<<15];
vector<vector<int> > vec(1<<15);
class CompanyMessages
{
        public:
        vector <int> getRank(vector <string> mes )
        {
            int n=mes.size();
            REP(mask,two(n)){
                if(!mask)continue;
                A[mask]=100000;
                REP(i,n)if(contain(mask,i)){
                    int now=mask^two(i); int tmp=A[now];
                    REP(j,n)if(contain(now,j))tmp+=(mes[j][i]-'0');
                    if(tmp<A[mask]){
                        vec[mask].clear();vec[mask].push_back(i);
                        for(int s=0;s<vec[now].size();s++)vec[mask].push_back(vec[now][s]);
                        A[mask]=tmp;
                    }
                }
            }
            return vec[two(n)-1];
        }

 

Code Snippet

int memo[two(15)],record[two(15)];
VS M;int N;VI ans;
int solve(int now){
    if( now == 0 ) return 0;
    if( memo[now]>=0 )return memo[now];
    memo[now] = 100000;
    REP(i,N)if(contain(now,i)){
        int mask = now ^ two(i);int tmp = solve(mask);
        REP(j,N)if(contain(mask,j))tmp += (M[j][i] - '0');
        if(tmp < memo[now]) {
            memo[now]=tmp ;
            record[now] = mask;
        }
    }
    return memo[now];
}
void cacl(){
    int mask = two(N)-1;
    ans.clear();
    REP(i,N){
        int k = mask ^ record[mask];
        int cnt = -1; while(k>0){k>>=1;cnt++;}
        ans.push_back(cnt);
        mask=record[mask];
    }
}
class CompanyMessages
{
        public:
        vector <int> getRank(vector <string> mes)
        {
               M=mes;N=mes.size();
               memset(memo,-1,sizeof(memo));
               solve(two(N)-1);
               cacl();
               return ans;
        }

半夜12：00的比賽，開始就發現系統很慢，結果第一題沒法提交，然后退出重進退出重進·····server down·····

想起洗的衣服還沒拿，于是跑下去取衣服，看了會dota vod ，重新登入，比賽竟然繼續·····交了500 開始看1000 沒思路，凍死了。

challenge沒啥意思，都沒人在，250的太弱智都對的····由于中間出錯，這次srm not rated~~

250 pt 略過

500 pt

John and Brus have an interest in team sports tournaments. They are currently investigating a basketball tournament. Basketball is a team sport in which two teams of five players try to score points against one another by placing a ball through a ten foot high hoop. Basketball is one of the most popular and widely viewed sports in the world.

There are n teams in the tournament. Each pair of teams plays exactly two games against each other. In the first of these games, one of the teams is the host, and in the second, the other team is the host. Each game results in one team winning. There are no draws. After the tournament is over, the team with the highest total number of wins is crowned the winner.

The tournament is currently in progress and the current results are described in the vector <string> table. For each pair of distinct indices, i and j, the j-th character of the i-th element of tableis the result of the game where team i hosted team j. The result is 'W' if team i won, 'L' if team i lost, and '?' if the game hasn't been played yet. Assuming that every possible outcome is possible for the games that haven't been played yet, return the minimal number of total wins the tournament winner can have at the end of the tournament.

Definition

Class:
TheBasketballDivTwo

Method:
find

Parameters:
vector <string>

Returns:
int

Method signature:
int find(vector <string> table)

(be sure your method is public)

Constraints

-
table will contain between 2 and 5 elements, inclusive.

-
Each element of table will contain exactly n characters, where n is the number of elements in table.

-
The j-th character of the i-th element of table, where i and j are different, will be 'W', 'L', or '?'.

-
The i-th character of the i-th element of table will be 'X'.

數據量很小，找到未比的比賽場次 ，然后枚舉各種輸贏情況，更新解就可以了。或者循環2^n次，或者遞歸調用

1000 pt

n this tournament, each game results in either a victory for one team or a draw. If a team wins a game, it gains three points and its opponent gains no points. In case of a draw, each team gains one point. The score of a team is the sum of all the points it has gained from all its games. Each pair of teams can play against each other any number of times.

You are given a vector <int> points representing the current standings in the tournament. The i-th element of points is the score of the i-th team. You can assume that the points represent a valid state, i.e., intermediate standings that can be achieved in a tournament according to the rules described above.

Each team will play exactly one more game in the tournament, but it is not known what the matchups will be. After the tournament is over, the teams will be ranked by score. 1st place will go to the team with the highest score, 2nd place will go to the team with the second highest score, and so on. If two teams have the same score, the team with the lower number will place higher. For example, if team 0 and team 3 each have the highest score of 100 points, then team 0 will place 1st and team 3 will place 2nd.

John's favorite team is team 0, and he wants it to place as high as possible. Assuming that the remaining games can be scheduled arbitrarily and can end with any possible outcome, return the highest possible place for team 0 at the end of the tournament.

Definition

Class:
TheSoccerDivTwo

Method:
find

Parameters:
vector <int>

Returns:
int

Method signature:
int find(vector <int> points)

(be sure your method is public)

Constraints

-
points will contain between 2 and 50 elements, inclusive.

-
points will contain an even number of elements.

-
Each element of points will be between 0 and 1,000,000, inclusive.

-
points will represent a valid state.

Examples

因為每隊只剩下一場比賽，所以題目變得很簡單。0隊最后一輪肯定是取到3分，比0隊多3場以上比賽的 肯定比0隊靠前，比0隊分少或者相等的一定在0隊之后，剩下的就是我們要考慮的了。如果A3+L+1>=E3 也就是說比0隊多勝一場的隊伍，如果讓他們在最后一輪都輸，那么0隊可以獲得最好成績 A3+1;

然而如果不行剩下的這些E3要有一半(E3+1)/2個要得到3分從而比0隊高，over~

昨天看了sedgewick的alg in c 的第一章，主要介紹了個find-union 判斷聯通的算法，其實用到了并查集的知識

剛才偶然看見poj并查集的題集 就copy過來自己也寫寫看~~·

慢慢來~~ 寫完一道上一道~~

       POJ 1182 食物鏈
http://acm.pku.edu.cn/JudgeOnline/problem?id=1182

還以為是最簡單的一道呢，被列在最前面，原來是擴展的應用，不是那么直接啊~

糾結了一會兒，看了解題報告才有思路。關鍵是在并查集的基礎上增加一個數組，維護其與根節點的關系；

詳情寫到注釋里面吧：

int A[100003][3];
int root[50005],k[50005];//root記錄節點所屬于的樹木id k記錄節點與根的關系0 同類1子是食物2子是天敵
int sz[50005];
int find(int x){
    if(root[x]==x)return x;//如果是根則返回
     else if(root[root[x]]==root[x])return root[x];//如果第一層，則返回
    int father=root[x];
    root[x]=find(father);//放到第一層，減少下次find時間，減小樹的高度
    k[x]=(k[x]+k[father])%3;//由自己與根的關系以及父節點與根的關系推斷出新的自己與根的關系，實際上是為了解決union后的節點與根的關系

                                            //因為union后，非根節點并沒有更新k，因此需要在此處處理更新
    return root[x];
}
inline void Union(int x,int y,int kind){
    int a=find(x);int b=find(y);
     if(sz[a]>sz[b]){//判斷后決定，要把size小的放到size大的上去，優化作用不大
    root[b]=a ; //b成為a的子樹
    k[b]=(k[x]-k[y]+kind+3)%3;//要把b變成a的子樹，從a出發，到x，經過kind，到y，再到b ，可以得到kb的狀態改變公式
    sz[a]+=sz[b];}
    else{
        if(kind==1)kind=2;
        root[a]=b;
        k[a]=(k[y]-k[x]+kind+3)%3;
        sz[b]+=sz[a];
    }
}
int main()
{
    int N,d;
    freopen("d:\\input.txt","r",stdin);
    scanf("%d %d",&N,&d);
    for(int i=1;i<=N;i++)sz[i]=1;
    int cnt=0;
     for(int s=1;s<=N;s++)root[s]=s;
    int LIE=0;
    int i=0;
    while(i !=d) {
        scanf("%d %d %d",&A[i][0],&A[i][1],&A[i][2]); 
        if(A[i][1]>N || A[i][2]>N ) {LIE++;i++;continue;}
        if(A[i][0]==1){
            if(find(A[i][1]) == find(A[i][2])){
                if(k[A[i][1]]!=k[A[i][2]]) LIE++;
            }
            else   Union(A[i][1],A[i][2],0); 
         }
        else{
            if( find(A[i][1])==find(A[i][2]) ){if(k[A[i][2]] != ( k[A[i][1]]+1)%3)LIE++;}
            else  Union(A[i][1],A[i][2],1); 
        }
    i++;
    }
    cout<<LIE<<endl;
    return 0;
}

http://acm.pku.edu.cn/JudgeOnline/problem?id=1611

 int G[30005];
 int sz[30005];
 int Find(int x){
    if(G[x]==x)return x;
    else {
        while(G[x]!=x){//half路徑壓縮~等下試試看全壓縮的效率~那樣就是遞歸調用啦
            int t=G[x];
            G[x]=G[t];
            x=t;
        }
        return x;
    }
 }
 void Union(int x,int y){
    if(sz[x]<sz[y])swap(x,y);//把size小的弄到大的上面
    G[y]=x;
    sz[x]+=sz[y];
 }
   int main()
{
    freopen("d:\\input.txt","r",stdin);
    int N,M,num;
    while(true){
        scanf("%d %d",&N,&M);
        if(N==0&&M==0)return 0;
        for(int i=0;i<N;i++)G[i]=i,sz[i]=1;
        for(int i=0;i<M;i++){
            scanf("%d",&num);
            int root,stu,x,y;
            for(int j=0;j<num;j++){
                scanf("%d",&stu);
                if(j==0)root=Find(stu);//簡單的都和第一個合并
                else{
                    root=Find(root);
                    x=Find(stu);if(root!=x)Union(root,x);
                }
            }
        }
        printf("%d\n",sz[Find(0)]);
    }
}

POJ 2524 Ubiquitous Religions

又一道水題~~ 呵呵 

不貼代碼了 和上面一道基本一樣~
http://acm.pku.edu.cn/JudgeOnline/problem?id=2524

POJ 1861

http://acm.pku.edu.cn/JudgeOnline/problem?id=1861

kruskal+并查集+half路徑壓縮

比較基礎的題

struct Edge{
    int from;
    int to;
    int value;
}E[15000];
int A[1005]; 
int sz[2009];
bool comp(const Edge& a,const Edge& b){
    return a.value<b.value;
}
using namespace std; 
int Find(int x){
    if(A[x]==x)return x;
    else if(A[A[x]]==A[x]) return A[x];
    int father;
    while(A[x]!=x){
        father=A[x];
        A[x]=A[father];//把每一個路過的節點放到祖父下面去
        x=father;
    }
    return x;
}
void Union(int x,int y){
    if(sz[y]>sz[x])swap(x,y);//小的放到大的下面
    sz[x]+=sz[y]; 
    A[y]=x;    
}
   int main()
{
    freopen("d:\\input.txt","r",stdin);
    int N,M,num,x,y;
    scanf("%d %d",&N,&M);
    int cnt=0;
    while(cnt<M)  scanf("%d %d %d",&E[cnt].from,&E[cnt].to,&E[cnt].value),cnt++;
    sort(E,E+M,comp);//從小到大選n-1條邊，如果起點和終點在一個集合則continue；else Union
    for(int i=0;i<=N;i++)sz[i]=1,A[i]=i;
    vector<int> ans(N-1);
    int mst=0,MX=0;
    for(int i=0;mst!=N-1;i++){
        int x=Find(E[i].from);int y=Find(E[i].to);
        if(x==y)continue;
        Union(x,y);
        ans[mst]=i;
        mst++;
        if(E[i].value>MX)MX=E[i].value;
    }
    printf("%d\n%d\n",MX,N-1);
    for(int i=0;i<N-1;i++)
        printf("%d %d\n",E[ans[i]].from,E[ans[i]].to);
}

        POJ 1456 Supermarket
http://acm.pku.edu.cn/JudgeOnline/problem?id=1456
 

       POJ 1733 Parity game
http://acm.pku.edu.cn/JudgeOnline/problem?id=1733
 

       hdu 3038 How Many Answers Are Wrong
http://acm.hdu.edu.cn/showproblem.php?pid=3038
 

     POJ 1417 True Liars(難)
http://acm.pku.edu.cn/JudgeOnline/problem?id=1417
 

   POJ 2912 Rochambeau(難)

http://acm.pku.edu.cn/JudgeOnline/problem?id=2912

Your restaurant has numTables tables to seat customers. The tables are all arranged in a line. If a large party of customers comes in, a group of adjacent tables will be used. Which group of tables is entirely up to the customer. Since you cannot predict this, assume all possible choices occur with equal probability. What you can predict is the size of each group of customers that arrives. Element i of probs gives the probability, in percent, that an entering party will need i+1 tables. Assuming nobody leaves, return the expected number of tables you will use before a party must be turned away. This only occurs if there is no place to seat them.

Method signature:
double getExpected(int numTables, vector <int> probs)

numTables will be between 1 and 12 inclusive.
probs will contain between 1 and 12 elements inclusive.
Each element of probs will be between 0 and 100 inclusive.
The elements of probs will sum to 100.

misof 數字表達教程里的習題~ 題目大意 求使用桌子的期望。由于到來group的個數不定，每個group需要的桌子不定，使確定期望變得困難。但考慮對于numTables來說,使用桌子的狀態僅僅有 2^numTables種，因此考慮在這些狀態改變的過程中來計算期望，也就是計算在每個狀態下面的期望桌子數目。在每個狀態到達時，依次考慮來了一個group需要k個位子，如果r種安排可以滿足k個位子，那么當前狀態的期望值要加上 來k個位子的概率 X （r種安排分別的期望和 / r） 其中求r中安排期望和則需要 遞歸調用函數。顯然利用memo可以減少重復計算于是有下面的解法：

vector<double> p;
double dp[1<<13];   
int tb;
double solve(int cur){
    if(dp[cur]>-1.0)return dp[cur];    //memo available
    double ret=0;double sum;int kind;
    for(int i=0;i<p.size();i++){
        sum=0,kind=0;
        int mask=(1<<(i+1))-1;    //new group need i+1 adjacent tables
        for(int j=0;j+i+1<=tb;j++){
            if((cur&(mask<<j))==0){    //current pattern could meet the need
                sum+=solve(cur+(mask<<j))+i+1;    //total method ++
                kind++;
            }
        }
        if(kind!=0)sum/=kind; //caculate the average need
        ret+=sum*p[i];
    }
    dp[cur]=ret;
    return ret;
}

        double getExpected(int numTables, vector <int> probs)
        {
                tb=numTables;
                REP(i,1<<13)dp[i]=-1.0;
                p.resize(probs.size());
                for(int i=0;i<probs.size();i++)p[i]=probs[i]*0.01;
                return solve(0);//the beginning pattern
        }

看比賽中有另一種解法，即根據題目，在到達每次fail to serve a group 的時候 根據此時的桌子數量，和到達這種狀態的概率 來計算：

dp[1<<13][15];memset(dp,0,sizeof(dp));// :D lucily I can do this for 0

double fails=0.0;bool flag ;

for(int i=1;i<=numTables+1;i++)  //循環最多numTables+1 次

{flag=true;

for(int j=0;j<p.size();j++){

     int mask=(1<<(j+1))-1;//注意移位運算符的優先級低,注意加括號

     for(int k=0;k<=(1<<numTables-1);k++){

          if(dp[k][i-1]<=0.0)continue;

          flag=false;

          int cnt=0;

          for(int m=0;m+j+1<=numTables;m++) if((mask<<m)&k==0)cnt++;

          if(cnt)for(int m=0;m+j+1<=numTables;m++)if((mask<<m)&k==0)dp[mask<<m|k][i]+=dp[k][i-1]*p[j]/cnt;

          if(!cnt){

                 int b=k,bn=0;while(b){if(b&1)bn++;b>>=1;}

                 fail+=dp[k][i-1]*bn; 

         }

    }

}

if(flag)return fail;//all dp[][k]==0.0

}

return fail;

優先級很容易錯：

http://www.cppreference.com/wiki/operator_precedence~。~

典型的幾個

++ -- <post-incre-decre>

~ <bitwise complement> !<not>&<addresss> *<dereference>&<address>

*  / %

+ -

>>  <<

< <= > >=

== !=

&

^ xor

|

&&

||

?=

= += –= <<= >>=

,

從上到下依次降低~~~~~~~~~~~~~~~~~~··

周六第一次做usaco玩，bronze的輕松切掉，然后申請promote，下午批準，話說rob 效率好高啊~ 于是繼續做silver 就遇到這個題- -！糾結了半天放棄····知道是dp 也考慮了方法就是 理不清楚；不知道是不是一天沒吃飯的緣故·····

今天題解出來了~ 先看了大概思路 然后自己寫出來了~

題目：

Farmer John's cows like to play coin games so FJ has invented with
a new two-player coin game called Xoinc for them.

Initially a stack of N (5 <= N <= 2,000) coins sits on the ground;
coin i from the top has integer value C_i (1 <= C_i <= 100,000).
The first player starts the game by taking the top one or two coins
(C_1 and maybe C_2) from the stack. If the first player takes just
the top coin, the second player may take the following one or two
coins in the next turn. If the first player takes two coins then
the second player may take the top one, two, three or four coins
from the stack. In each turn, the current player must take at least
one coin and at most two times the amount of coins last taken by
the opposing player. The game is over when there are no more coins
to take.

Afterwards, they can use the value of the coins they have taken
from the stack to buy treats from FJ, so naturally, their purpose
in the game is to maximize the total value of the coins they take.
Assuming the second player plays optimally to maximize his own
winnings, what is the highest total value that the first player can
have when the game is over?

MEMORY LIMIT: 20 MB

PROBLEM NAME: xoinc

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single integer: C_i

SAMPLE INPUT (file xoinc.in):

5
1
3
1
7
2

簡單來說就是兩個人輪流取coins，每個人每次取得個數為1- 2*n;n為上一輪對方取得數目，

求兩個人都是用最佳策略，先取得那個家伙最多能拿到多少硬幣。貌似可以算是簡單博弈論的思想

思路：

        coins[1···N] 從下到上 sum[1···N] 剩下 i個的和

        找到無后效性的子問題。考慮在還剩下p個錢幣時候的情況，此時可以拿k個錢

由于條件，k的大小受上一輪拿的個數i的限制 ，所以我們要加上一個變量i。得到

dp[p][i]這個子問題。那么容易得到

dp[p][i]=max(1=<k<=i*2){SuM(p to p-k+1)+SuM(p-k to 1)-dp[p-k][k]}

            =max(1=<k<=i*2){sum[p]-dp[p-k][k]}

按照這個可以得到一個O（N^3）的算法

oidsolve(){
   for(inti=1;i<=N;i++)//剩下i個
        for(intj=1;j<=N;j++)//上一人拿了j 個
            for(intk=1;k<=j*2&&i-k>=0;k++){
                dp[i][j]=max(dp[i][j],sum[1]-sum[i+1]-dp[i-k][k]);
            }
    ret=dp[N][1];
}

 三重遞歸 ，最多可以過500的數據量  觀察可以得出 dp[p][j] 和 dp[p][j+1] 的計算有很多的重疊
因為 上次拿了j+1 則可以比 dp[p][j] 多拿 2 個 

然后，由于考慮j的范圍 應該為 N-i+1

這樣得到了最終代碼：

scanf("%d",&N);
for(int i=1;i<=N;i++)    scanf("%d",coins+i);//{fin>>coins[i]; }
sum[0]=0;
for(int i=1;i<=N;i++)     sum[i]=sum[i-1]+coins[N-i+1]; 
for(int i=1;i<=N;i++)        //剩下i個
for(int j=1;j<= N-i +1;j++){ // 上次拿了j個
if(dp[i][j]<dp[i][j-1])dp[i][j]=dp[i][j-1];
if(2*j-1<=i&&dp[i][j]<sum[i]-dp[i-2*j+1][2*j-1]) dp[i][j]=sum[i]-dp[i-2*j+1][2*j-1];
if(2*j<=i&&dp[i][j]<sum[i]-dp[i-2*j][2*j]) dp[i][j]= sum[i]-dp[i-2*j][2*j];
}
printf("%d\n",dp[N][1]);

很晚了 ，先寫這么多 ，有空把bronze的寫了

3個月后注：事實證明，當時么有時間 ~以后更沒有時間 ~~~ hoho`````````~~~~~~~``````````

Steps to developing a usable algorithm.
• Define the problem.
• Find an algorithm to solve it.
• Fast enough?
• If not, figure out why.
• Find a way to address the problem.
• Iterate until satisfied.

主要內容 FIND-UNION ALGORITHM

就是利用并查集來考察連通性的算法 。條件N個節點，M對節點，輸入每一對節點時候，如果已經連通，則忽略，否則輸出接點并更新

主要介紹三種算法：第一種，QUCK-FIND 利用數組記錄每一個聯通子圖，同一個聯通子圖的節點數組變量是相同的。因此每讀入一對就需要遍歷N個數組變量考察是否需要更新，最壞時間MN，實際上每個子圖為高度為2的樹;第二種，QUICK-UNION 聯通子圖需要union時 僅僅需要將兩個root union 因此每個聯通子圖高度變高，所有find root 會消耗一定時間，當然無需遍歷N了 ，最壞時間，也就是每次均需要從葉子節點去回溯求根（這里書中舉得例子好像有問題）也是MN；第三種也就是 QUICK WEIGHT UNION 這種方法在兩個子樹合并的時候，不是簡單的指定合并策略，而是經過判斷的，把size小（相應高度也小）的合并到size大的里面；實際上很容易理解就是盡量減少樹的高度來追求quick-find的效率；

進而作者寫道路徑壓縮，也是這種思想。或者實現為全部壓縮，也就是說在進行union操作的時候，所有check的節點都直接鏈接到union后的新root下面，或者half union （容易實現且性能好）每次check時候，如果沒有停止loop簡單的令 id[i]=id[id[i]];即可達到減少到根距離的效果。

half union 的主要代碼：

int i,j;
for(i=p;id[i]!=i;i=id[i]) id[i]=id[id[i]];
for(j=p;id[j]!=j;j=id[j]) id[j]=id[id[j]];
if(i==j)continue;
if(size[i]>size[j]) id[j]=i,size[i]+=size[j];
else        id[i]=j,size[j]+=size[i];

第一次用windows live writer 試試效果哦~~