UVa 11069 A Graph Problem

題意：

1. 子集合內數字不能相鄰
2. 要盡可能填滿，比如n=6，那麼就不能有{3,6}而是要{1,3,6}，不能是{1,4}而是要{1,4,6}

想法：

　　一開始很直覺的使用遞迴一直往下尋找，但是使用遞迴會TLE，換個想法，很類似高中排列組合的階梯問題，本題是一次走2階或3階：

• n=1{1} : 1
• n=2{1,2} : 2
• n=3{1,2,3} : 2
• 當n=4{1,2,3,4}，有哪些情況會選到'4'? n=1({1,4})或n=2({2,4})的情況，所以n(4)=n(1)+n(2)=3
• 當n=5{1,2,3,4,5}，會選到'5'的情況有n=2({2,5})或n=3({1,3,5})，所以n(5)=n(2)+n(3)=4
• 以此類推..

	#include <cstdio>
	using namespace std;
	int main()
	{
	int ans[77];
	ans[1]=1;
	ans[2]=2;
	ans[3]=2;
	for(int i=4;i<=76;i++)
	ans[i]=ans[i-2]+ans[i-3];
	int n;
	while(scanf("%d",&n)!=EOF)
	printf("%d\n",ans[n]);
	return 0;
	}
	//*********遞迴版**********
	#include <cstdio>
	using namespace std;
	void graph(int n,int i);
	int numOfSub;
	int main()
	{
	int n;
	while(scanf("%d",&n)!=EOF){
	numOfSub=0;
	for(int i=1;i<=2&&i<=n;i++)
	graph(n,i);
	printf("%d\n\n",numOfSub);
	}
	return 0;
	}
	void graph(int n,int i)
	{
	if(i+2>=n){
	numOfSub++;
	return;
	}
	graph(n,i+2);
	graph(n,i+3);
	}

view raw [UVa] 11069 A Graph Problem.cpp hosted with ❤ by GitHub