E - Lucky Numbers

传送门：

E - Lucky Numbers

题意：给你一个长为n-1的序列s，还有一个长为m的x序列，他们被称为幸运数字。

定义一个长为n的序列a满足下列条件那么这是一个好序列：

a[i]+a[i+1]=s[i]

构造一个好序列使得序列中有最多的数字是幸运数字。

分析：m<=10，考虑枚举，把每个a[i]=x[j]。容易发现确定a序列的一个值就能确定a序列，也就是可以说a序列的特征值是a[1]。假设最优解的序列是a[1],a[2],s[3]...，那么当且仅当a[i]=a[i]的时候这个序列出现一次，至此，可以将问题转化为 求出现最多的序列的次数。用map和特征值求解即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int sum[100005];
int ss[100005];
int x[15];
map<int,int>mp;

signed main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n-1;i++)
	{
		cin>>sum[i];
	}
	for(int i=2;i<=n;i++)
	{
		ss[i]=sum[i-1]-ss[i-1];
	}
	for(int i=1;i<=m;i++)
	{
		cin>>x[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			int now=x[j];
			int tmp;
			if(i%2) tmp=now-ss[i];
			else tmp=ss[i]-now;
			mp[tmp]++;
		}
	}
	int maxx=0;
	for(auto it:mp)
	{
		maxx=max(maxx,it.second);
	}
	cout<<maxx<<endl;
}