LightOJ 1173 The Vindictive Coach (DP 计数)

悠悠 2022-12-24 00:53 112阅读 0赞

题目连接：http://lightoj.com/volume\_showproblem.php?problem=1173

题意：n个不同身高的队员和教练的按照身高排成波浪形……每个人按照身高由低到高编号，其中第m个是教练，他必须在第一个，如果条件允许，排第二的要比m低，如果条件不允许，即其余人都比教练高，则要让差距尽可能小。

思路：其实就是n个不同的数排成波浪形。

f\[n\]\[i\]表示n个数以第i个开始前两个数升序的个数；f\[n\]\[i\]=sigma(g\[n-1\]\[j\])(i<=j<=n-1)

g\[n\]\[i\]表示n个数以第i个开始前两个数降序的个数；g\[n\]\[i\]=sigma(f\[n-1\]\[j\])(1<=j<=i-1)

这里有一篇英文的博文写得很好，貌似要翻墙……http://lbv-pc.blogspot.com/2012/09/the-vindictive-coach.html

要用无符号64位整型数

一组测试数据：

Input：

16  
3 1  
3 3  
4 1  
5 3  
4 3  
4 4  
22 10  
22 22  
22 21  
22 20  
22 17  
10 9  
10 10  
1 1  
5 1  
22 1

Out

Case 1: 1  
Case 2: 1  
Case 3: 1  
Case 4: 4  
Case 5: 2  
Case 6: 2  
Case 7: 4199654144  
Case 8: 2056257536  
Case 9: 2056257536  
Case 10: 2984640512  
Case 11: 4104847360  
Case 12: 7936  
Case 13: 7936  
Case 14: 1  
Case 15: 1  
Case 16: 3366584320

#include <cstdio>
    #define __int64 unsigned long long
    
    int n,m;
    __int64 f[52][52],g[52][52];
    
    void Init ()
    {
    	f[1][1]=1;
    	g[1][1]=1;
    	for (int n=2;n<=50;n++) for (int i=1,j;i<=n;i++)
    	{
    		for (j=i;j<=n-1;j++) f[n][i]+=g[n-1][j];
    		for (j=1;j<i;j++) g[n][i]+=f[n-1][j];
    	}
    }
    
    __int64 DP ()
    {
    	__int64 ans=0;
    	int i;
        if (m>1)
            for (i=1;i<=m-1;i++)
    			ans+=f[n-1][i];
    	else
    	{
    		if (n<=2) ans=1;
    		else ans=g[n-1][2];
    	}
    	return ans;
    }
    
    int main ()
    {
    #ifdef ONLINE_JUDGE
    #else
    	freopen("read.txt","r",stdin);
    #endif
    	Init ();
    	int T;
    	scanf("%d",&T);
    	for (int Cas=1;Cas<=T;Cas++)
    	{
    		scanf("%d%d",&n,&m);
    		printf("Case %d: %llu\n",Cas,DP());
    	}
    	return 0;
    }