ZOJ 3605 Find the Marble

题意:Alice和Bob在玩一个游戏，该游戏需要n个杯子和一个石头，开始时石头被罩在在某个杯子里，Alice可交换任意两个杯子，经过一系列的交换，由Bob猜石头在哪个杯子里，交换总共m步，但Bob只看到了其中的k步，问Bob猜哪个杯子的可能性最大。

第一感觉就是和组合（在n个数里取m个有多少种）很相似，再看题目因为顺序是一定的，即选了k步之后，顺序只有一种。

c[n][m]=c[n-1][m-1]+c[n-1][m];

具体编码的时候只考虑到交换的两个杯子而忘记其他杯子在选择时的值也要加上c[n-1][m-1];

 

#include<cstdio>
#include<cstring>
#define MAXN 55
using namespace std;

long long dp[MAXN][MAXN][MAXN];

int main()
{
    int T,n,m,s,k,i,j,t,a[MAXN],b[MAXN];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&n,&m,&k,&s);
        for(i=1;i<=m;i++)
            scanf("%d%d",a+i,b+i);
        memset(dp,0,sizeof(dp));
        dp[0][0][s]=1;
        for(i=1;i<=m;i++)
        {
            dp[i][0][s]=1;
            for(j=1;j<=i&&j<=k;j++)
            {
                dp[i][j][b[i]]=dp[i-1][j-1][a[i]];
                dp[i][j][a[i]]=dp[i-1][j-1][b[i]];
                for(t=1;t<=n;t++)
                {
                    dp[i][j][t]+=dp[i-1][j][t];
                    if(t!=a[i]&&t!=b[i])//最开始忘记考虑的一种情况
                        dp[i][j][t]+=dp[i-1][j-1][t];
                }
            }
        }
        /*for(i=1;i<=m;i++,putchar('\n'))
            for(j=0;j<=k;j++,putchar('\n'))
                for(t=1;t<=n;t++)
                    printf("%d ",dp[i][j][t]);
        printf("\n");*/
        for(s=1,t=2;t<=n;t++)
            if(dp[m][k][t]>dp[m][k][s])
                s=t;
        printf("%d\n",s);
    }
    return 0;
}