[遞推]1020 F.Number Insertion

Shaymin

原題：http://tioj.ck.tp.edu.tw/problems/1020
測試結果：http://tioj.ck.tp.edu.tw/submissions/2492


經觀察可以發現，一個K-合法序列是由K-1-合法序列加上K所形成的，經紙筆推演可發現答案增長的速度似乎不是很快，而且測資有限，於是我們可以離線計算後直接輸出答案。

如果這篇code在哪看過了，就當作是個秘密吧！

[C++] 純文本查看 復制代碼

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool cmp(const vector<int> &a,const vector<int> &b)
{
	int i=0;
	while(true){
		if(a[i]!=b[i])
			return a[i]>b[i];
		++i;
	}
	return false;
}
int main()
{
	vector<vector<int>> D[32];
	vector<int> tmp;
	D[1].push_back({0,1});
	for(int i=2;i<=31;++i)
	{
		for(const auto &d : D[i-1])
		{
			for(int j=0;j<d.size()-1;++j)
			{
				if(i%(d[j]+d[j+1])==0)
				{
					tmp=d;
					tmp.insert(tmp.begin()+j+1,i);
					D[i].push_back(tmp);
				}
			}
		}
		sort(D[i].begin(),D[i].end(),cmp);
		cout<<"\"";
		cout<<D[i].size()<<"\\n";
		for(auto j:D[i][0])
			cout<<j<<' ';
		cout<<"\\n\","<<endl;;
	}
	return 0;
}

[C++] 純文本查看 復制代碼

#include<cstdio>
char ans[][1000]={
"",
"1\n0 1\n",
"1\n0 2 1\n",//2
"1\n0 2 3 1\n",
"2\n0 4 2 3 1\n",
"3\n0 4 2 5 3 1\n",
"4\n0 6 2 5 3 4 1\n",
"6\n0 6 2 7 5 3 4 1\n",
"12\n0 8 4 6 2 7 5 3 1\n",
"12\n0 8 4 6 2 9 7 5 3 1\n",
"23\n0 10 2 3 4 9 5 6 7 8 1\n",
"33\n0 10 2 3 4 9 5 11 6 7 8 1\n",
"65\n0 12 6 8 10 2 11 9 7 5 3 4 1\n",
"87\n0 12 6 8 10 2 13 11 9 7 5 3 4 1\n",
"200\n0 14 2 12 10 13 3 4 9 5 11 6 7 8 1\n",
"226\n0 14 2 15 3 4 5 6 13 7 8 9 10 11 12 1\n",
"460\n0 16 8 12 4 14 10 6 2 15 13 11 9 7 5 3 1\n",
"614\n0 16 8 12 4 14 10 6 2 17 15 13 11 9 7 5 3 1\n",
"1247\n0 18 6 16 2 17 15 13 11 9 7 12 5 8 3 14 4 10 1\n",
"1548\n0 18 6 16 2 19 17 15 13 11 9 7 12 5 8 3 14 4 10 1\n",
"3032\n0 20 10 12 14 16 18 2 19 17 15 3 4 13 9 5 11 6 7 8 1\n",
"3721\n0 20 10 12 14 16 18 2 21 19 17 15 3 4 13 9 5 11 6 7 8 1\n",
"8035\n0 22 2 20 18 16 14 12 10 3 21 4 9 5 11 17 6 19 13 7 15 8 1\n",
"12195\n0 22 2 20 23 3 21 4 18 5 6 7 8 17 9 19 10 11 12 13 14 15 16 1\n",
"21696\n0 24 12 18 6 22 16 2 23 21 19 17 15 13 11 20 9 7 5 8 3 14 4 10 1\n",
"26492\n0 24 12 18 6 22 16 2 25 23 21 19 17 15 13 11 20 9 7 5 8 3 14 4 10 1\n",
"53504\n0 26 2 25 3 24 21 4 5 22 6 7 8 9 10 11 23 12 13 14 15 16 17 18 19 20 1\n",
"71264\n0 26 2 27 25 3 24 21 4 5 22 6 7 8 9 10 11 23 12 13 14 15 16 17 18 19 20 1\n",
"147392\n0 28 14 16 18 20 22 24 26 2 27 25 23 21 19 17 15 3 4 5 6 13 7 8 9 10 11 12 1\n",
"216653\n0 28 14 16 18 20 22 24 26 2 29 27 25 23 21 19 17 15 3 4 5 6 13 7 8 9 10 11 12 1\n",
"372984\n0 30 10 22 12 28 2 29 27 25 3 24 21 4 26 9 23 14 19 5 16 11 17 6 13 20 7 15 8 18 1\n",
"365437\n0 30 10 22 12 28 2 31 29 27 25 3 24 21 4 26 9 23 14 19 5 16 11 17 6 13 20 7 15 8 18 1\n",};

int main()
{
	int p;
	scanf("%d",&p);
	printf(ans[p]);
}