E - Lucky Numbers

Portal ：

E - Lucky Numbers

The question ： Here's a long one for you n-1 Sequence s, There is also a long m Of x Sequence , They are called lucky numbers .

Define a length of n Sequence a If the following conditions are met, then this is a good sequence ：

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

Construct a good sequence so that the most numbers in the sequence are lucky numbers .

analysis ：m<=10, Consider enumeration , Put each a[i]=x[j]. It is easy to find and determine a A value of the sequence can be determined a Sequence , That is to say a The eigenvalue of the sequence is a[1]. Suppose the sequence of the optimal solution is a[1],a[2],s[3]..., So if and only if a[i]=a[i] This sequence appears once , thus , You can turn the problem into Find the number of the most frequent sequences . use map And eigenvalues .

Code ：

#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;
}