hdu 3406 Baseball of Planet Pandora

Problem Description
The baseball game of planet Pandora is similar to the game of the Earth. In the game field, there are four bases which are named “home base”, “first base”, “second base” and “third base”. At the beginning, nobody is on the bases. There are two teams, one is the attacking team, and the other is the defending team.
One by one, all players of the attacking team goes to the home base and bats the ball thrown by the defending team.
There are four possible results of a bat:
1. “Out”. In this case, the batter misses the ball, so he is disqualified and leaves the game.
2.“Bingle”. In this case, the batter hits the ball, but the ball doesn’t fly out of the field. Then the batter can advance to the first base, and other players of the attacking team who are already on a base can advance to next base (The next base of the third base is the home base). If a player returns to the home base, he scores one point for his team.
3.“Allrun”. In this case, the batter hits the ball out of the field and then all the players on the bases (including the batter) can run to the home base and each scores one point for his team. So in this case, the attacking team can score at least 1 point, and at most 4 points.
4.“Sacrifice”. In this case, the batter chooses not to bat and leaves the field. According to the rule, in this case, the players still on the bases can advance to next base. So the player advancing to the home base this way scores one point. But if there have already been two batters who get an “Out” or a “Sacrifice” before, “Sacrifice” will end the game immediately and the attacking team can’t score any point in this “Sacrifice”.
  According to the rule, a player must leave the field immediately after he scores one point for his team. The game ends after every player of the attacking team has batted once(A “Sacrifice” is also regarded as a bat), or after there has been 3 batters who get an “Out” or an “Sacrifice”.
Avatar is the coach of an attacking team. He knows that the same player performs differently when the player takes different turns. For example, if you let Jack to be the first batter, he will definitely get an “Out”, but if you let him play in the third turn, he will get an “Allrun”. Avatar knows his men very well. He asked you to find out the best “batting order” for his team. If the team bats in that order, their score will be maximized.
 
Input
There are multiple test cases, ended by 0.
For each test case:
The first line contains an integer n(1<=n <=15), meaning the number of players in Avatar’s team. All players are numbered for 1 to n.
Then a n×n matrix A follows. Aij describes what result the player i will get if he is the jth batter.( i and j start from 1 )
Following is the meaning of the value of Aij:
0 means the result is “Out”
1 means the result is “Sacrifice”
2 means the result is “Bingle”
3 means the result is “Allrun”
 
Output
For each test case, print one line containing the highest score Avatar’s team can get in the game.
 
Sample Input

   
   
   
   

    
    
    
    5
0 2 0 1 2
1 0 2 0 2
0 2 1 2 0
0 2 2 1 2
2 1 0 2 0
0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    2
   
   
   
   

 
Source
2010 National Programming Invitational Contest Host by ZSTU
 
Recommend
wxl
오래 끌었는데, 이 문제는... 줄곧 여러 학교의 시합이 있어서, 줄곧 할 시간이 있었는데, 어제 뒤에서 앞으로 과감하게 밀어내서, 오늘 다시 A를 썼다.
분명히 상태 dp.
제목은 i개인이 j번째 공을 치는 상황을 알려주고 어떻게 군대를 배치하여 총 득점을 가장 높일 수 있는지 묻는 것이다.
0이 되면 스트라이크 아웃
1은 타격하지 않고 자신이 퇴장한다는 것을 의미하지만 루상에 있는 모든 선수가 다음 루상에 도착해 홈에 도착하는 가산점, 이 타자는 아웃이다. 그러나 이 타자가 아웃된 후 아웃된 사람이 3명에 이르면 가산점을 주지 않고 경기가 바로 끝난다
2는 타격 성공, 타자 출루, 모든 주자가 다음 베이스에 도달, 홈에 도달 +1점
3은 홈런을 의미하며, 모든 주자가 홈으로 달려가 점수를 주고, 타자도 1, 2, 3루에서 홈으로 달려가 점수를 얻는다.
경기가 끝난 상황은 모든 n명이 다 치거나 3명이 아웃될 수 있다.
dp[i][j][k]는 상태가 i이고 3루의 상태는 j로 이미 k 개인에서 가장 많은 점수를 얻었다.전체적으로 간단합니다. 다음 사항을 주의하십시오.
1. 비트 수조를 미리 처리한다. 즉, 각 2진수는 몇 개의 1이 있는지, 순환에서 계산하면 많은 수가 중복되기 때문에tle.
2. 비트 연산의 우선순위가 극도로 낮다...개수조를 할 때(1<15)+2 괄호를 잊어버리고 과감하게 제출한다.
코드

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int dp[(1<<16)+2][10][4];
int map[17][17];
int bit[(1<<16)+2];

int main()
{
    int i,j,n,cnt,k,l,m,p,a,ans;
    for (i=0;i<(1<<16);i++)
    {
        cnt=0;
        for (j=0;j<16;j++)
        {
            if ((i & (1<<j))!=0) cnt++;
        }
        bit[i]=cnt;
    }
    while(1)
    {
        scanf("%d",&n);
        if (n==0) break;
        for (i=0;i<n;i++)
        {
            for (j=0;j<n;j++)
            {
                scanf("%d",&map[i][j]);
            }
        }
        memset(dp,-1,sizeof(dp));
        ans=0;
        dp[0][0][0]=0;
        for (i=0;i<(1<<n);i++)
        {
            for (j=0;j<(1<<3);j++)
            {
                for (k=0;k<3;k++)
                {
                    if (dp[i][j][k]==-1) continue;
                    ans=max(ans,dp[i][j][k]);
                   // printf("%d...%d...%d...%d
",i,j,k,dp[i][j][k]);
                    if (k==3) continue;
                    for (l=0;l<n;l++)
                    {
                        if ((i & (1<<l))!=0) continue;
                        p=(i | (1<<l));
                        cnt=bit[p]-1;
                        if (map[l][cnt]==0)
                        {
                            dp[p][j][k+1]=max(dp[p][j][k+1],dp[i][j][k]);
                        }
                        if (map[l][cnt]==1)
                        {
                            if (k==2) continue;
                            if ((j & 4)!=0) dp[p][(j<<1) & 7][k+1]=max(dp[p][(j<<1) & 7][k+1],dp[i][j][k]+1);
                            else dp[p][(j<<1) & 7][k+1]=max(dp[p][(j<<1) & 7][k+1],dp[i][j][k]);
                        }
                        if (map[l][cnt]==2)
                        {
                       //     printf("%d...%d...%d....%d.....%d....%d
",p,((j<<1)&7)+1,k,dp[i][j][k],cnt,l);
                            if ((j & 4)!=0) dp[p][((j<<1) & 7)+1][k]=max(dp[p][((j<<1) & 7)+1][k],dp[i][j][k]+1);
                            else dp[p][((j<<1) & 7)+1][k]=max(dp[p][((j<<1) & 7)+1][k],dp[i][j][k]);
                        }
                        if (map[l][cnt]==3)
                        {
                            dp[p][0][k]=max(dp[p][0][k],dp[i][j][k]+((j & 1)!=0)+((j & 2)!=0)+((j & 4)!=0)+1);
                        }
                    }
                }
            }
        }
        printf("%d
",ans);
    }
    return 0;
}