【题解】UVA10930 A-Sequence

题意

判断一个序列是否满足两个条件：

1. 为递增序列。

2. 对于任意序列元素 (a_i) 不是之前的任何两个或多个元素之和。

分析

1. 为递增序列： 从前到后扫一遍，看是否有 (a_i > a_{i+1})。
2. 对于任意序列元素 (a_i) 不是之前的任何两个或多个元素之和： 采用 (dp) 的思路，将可以用前 (i) 个凑出来的数标记，看 (a_i) 是否被标记过。（具体实现看代码）

Code

#include <bits/stdc++.h>
using namespace std;

const int N = 35, M = 30005;

int a[N];
int f[M];
int t = 1,n;

void print(int flag)
{
	printf("Case #%d:",t ++);
	for (int i = 1; i <= n; i++) printf(" %d",a[i]);
	printf("
This is ");
	if (!flag) printf("not ");
	printf("an A-sequence.
");
	
	return ;
}

int main()
{
	while(cin>>n)
	{
		int sum = 0;
		for(int i=1;i<=n;i++) cin>>a[i],sum += a[i];

		int flag = 1;

		//是否升序
		for(int i=1;i<n;i++) 
		{
			if(a[i] > a[i+1])
			{
				flag = 0;
				break;
			}
		}
		
		memset(f,0,sizeof f);
		f[0] = 1;
		if(flag)
		{
			for(int i=1;i<=n;i++)
			{
				if(f[a[i]])
				{
					flag = 0;
					break;
				}
				for(int j = sum;j >= a[i];j--) if(f[j-a[i]]) f[j] = 1;
			}
		}

		print(flag);
	}

	return 0;
}