乱八七糟的代码

继续是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 试试效果哦~~