ZOJ—— 2625 Rearrange Them（dp）

「爱情、让人受尽委屈。」 2021-09-26 12:28 229阅读 0赞

题目链接：[http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2625][http_acm.zju.edu.cn_onlinejudge_showProblem.do_problemCode_2625]

题目：

Rearrange Them

--------------------

Time Limit: 2 Seconds      Memory Limit: 65536 KB

--------------------

N people stand in a line, and we numbered them 1,2...n, and now you are asked to rearrange them. The ith people is considred in the front of the (i+1)th, after the rearrange, everyone the people in front of whom can not be the same one as before. How many different strategies you can do the rearrange.

**Input:**

Each test case just contains one integer, the number of people you have to rearrange.

**Output:**

The number of strategies you have to rearrange them, with the condition above.

**Sample Input:**

3
    4

**Sample Output:**

3
    11

题目描述：

动态规划题，，给一个数n，重新排列1-n之间的数，要求 i 和 i + 1(i < n)不能是顺序的，比如n=3时，排列有123、132、213、231、312、321，其中123、231、312是不符合要求的。

这题我是找规律硬找出来的，，，设f\[i\]为i个数时符合要求的数量，则状态转移方程为f\[i\] = f\[i-1\]\*(i-1)+f\[i-2\]\*(i-2).题目没有给出范围，一开始直接写的错了，后来用大整数写的，还有比较坑的是当n=1时，答案为0，，，啊，脑阔疼。

代码：

#include<stdio.h>
    #include<string.h>
    char f[1010][5010]={"0","0","1","3"};
    void cd(char a[],int b,char *asq)
    {
    	int i,j;
    	int w[5010],e[5010],q[10020];
    	memset(w,0,sizeof(w));
    	memset(e,0,sizeof(e));
    	memset(q,0,sizeof(q));
    	char ee[5010]={'\0'};
    	sprintf(ee,"%d",b);
    	for(i = 0;i < strlen(a);i ++)
    		w[strlen(a) - i - 1] = a[i] - '0';
    	for(i = 0;i < strlen(ee);i ++)
    		e[strlen(ee) - i - 1] = ee[i] - '0';
    	for(i = 0;i < strlen(a);i ++){
    		for(j = 0;j < strlen(ee);j ++){
    			q[i + j] += w[i] * e[j];
    		}
    	}
    	for(i =0;i < 10020;i ++){
    		if(q[i] >= 10){
    			q[i + 1] += q[i]/10;
    			q[i] = q[i]%10;
    		}
    	}
    	int sr = 0,k = 0;
    	for(i = 5010 - 1;i >= 0;i --){
    		if(sr){
    			asq[k++] = q[i] + '0';
    		}
    			
    		else if(q[i]){
    			asq[k++] = q[i] + '0';
    			sr = 1;
    		}
    	}
    	asq[k] = '\0';
    }
    void add(char a[],char b[],char *asq)
    {
    	int i;
    	int w[5010],e[5010],q[5010];
    	memset(w,0,sizeof(w));
    	memset(e,0,sizeof(e));
    	memset(q,0,sizeof(q));
    	for(i = 0;i < strlen(a);i ++)
    		w[strlen(a) - i - 1] = a[i] - '0';
    	for(i = 0;i < strlen(b);i ++)
    		e[strlen(b) - i - 1] = b[i] - '0';
    	for(i = 0;i < (strlen(b) > strlen(a) ? strlen(b) : strlen(a));i ++){
    		q[i] += w[i] + e[i];
    		if(q[i] >= 10){
    			q[i + 1] += q[i]/10;
    			q[i] = q[i]%10;
    		}
    	}
    	int sr = 0,k = 0;
    	for(i = 5010 - 1;i >= 0;i --){
    		if(sr){
    			asq[k++] = q[i] + '0';
    		}	
    		else if(q[i]){
    			asq[k++] = q[i] + '0';
    			sr = 1;
    		}
    	}
    	asq[k] = '\0';
    }
    int main()
    {
    
    	int i,a;
    	char x[5010],y[5010];
    	for(i = 4;i < 1010;i ++){
    		memset(x,'\0',sizeof(x));
    		memset(y,'\0',sizeof(y));
    		cd(f[i - 1],i - 1,x);
    		cd(f[i - 2],i - 2,y);
    		add(x,y,f[i]);
    	}
    	while(scanf("%d",&a)!=EOF){
    		printf("%s\n",f[a]);
    	}
    	
    	return 0;
    }

[http_acm.zju.edu.cn_onlinejudge_showProblem.do_problemCode_2625]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2625