[TIOJ] 1103. F.假日的奇想曲

題目連結:http://tioj.infor.org/problems/1103
先說顯然本題不能開一個$n \times 2n$的矩陣,不然你一定會MLE掉,那該怎麼做呢?
大家高中可能學過類似這種題目的做法:填格子,沒錯,就是填格子,每次從左到右填一橫條,把它下面跟他左邊(也就是相鄰的)的值加起來,那顯然我們每次都只會用到它下面那條,其他用完就可以扔了,所以不妨用兩條滾動,然後記得先把表完全建好,不然每次要問都要建一次,複雜度會變成$O(t \times n^2)$,明顯會慘掉..
#include <bits/stdc++.h>
using namespace std;
#define modBASE 10000
#define N 10000

int graph[2][N + 10];
int val[N + 10];

int main(){
	int sz=0;
	for(int i=0;i<=N;i++)
		graph[0][i]=1;
	for(int i=1;i<=2*N;i++){
		if((i-1)%2==0)sz++;
		for(int j=0;j<=N;j++)
			graph[i%2][j]=0;
		for(int j=sz;j<=N;j++){
			graph[i%2][j]=graph[i%2][j-1];
			graph[i%2][j]%=modBASE;
			graph[i%2][j]+=graph[(i-1)%2][j];
			graph[i%2][j]%=modBASE;
			if(j*2==i)val[j]=graph[i%2][j];
		}
	}
	int n;
	scanf("%d",&n);
	while(n!=0){
		if(n>=8)
			printf("%04d\n",val[n]);
		else
			printf("%d\n",val[n]);
		scanf("%d",&n);
	}
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology