5864. 【NOIP2018模拟9.11】很多序列

Description

Input

Output

Sample Input

2
4 7
           

Sample Output

17
           

Solution

對于n=2的情況我們在NOIP可以找到原題。

答案為a1*a2-a1-a2。

證明可以在正解中講。

設讀入的數分别是a1...a6。

相當于我們可以在其中選出若幹個數若幹次，得到一個和，求這個最大的不能取到的和。

我們設f[ i ]表示取數的和mod a1等于i的最小的取數之和。那麼我們可以用SPFA轉移，注意這裡轉移時必須記錄%a1的餘數，不能直接記錄原數，這樣就不能标記了。

最後我們取f[]數組裡最大的數減去a1即為答案。因為我們知道對于f[i]中的數，即%a1等于i的最小的數，它加上a1,2*a1,3*a1...的和這些數都是可以取到的，是以我們要求最大不能取到的數，就取f[i]的值減去a1的最大值就可以了。

最後，因為a1和a2是互質的。

我們按照正解的思路做SPFA,發現在dis中更新的數隻有a2,2*a2,3*a2,...(a1-1)*a2。因為（a1*a2）%a1=0,是以到a1-1就結束了。

我們又知道：

a2 %a1

2*a2 %a1

3*a2 %a1

...

(a1-1) * a2 %a1

的這些餘數互不相同。

考慮反證法。

假設 x不等于y且 x* a2同餘與 y*a2 (在模a1的意義下) 

則有  x 同餘與 y (在模a1的意義下)

因為x、y隻取[0..a1-1]

是以x=y。

與題設沖突。

是以，結論成立。

至此，我們知道了a2,2*a2,3*a2...(a1-1)*a2在模a1的意義下是互不相同的，是以更新的f數組中1—（a1-1）中的每一個位置都是在這些數中的其中一個，那麼f數組中的最大值就是(a1-1)*a2，将它減去a1即為答案。

是以答案就是(a1-1)*a2 -a1=a1*a2-a1-a2。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define N 1000000
#define I int
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define F(i,a,b) for(I i=a;i<=b;i++)
using namespace std;
ll n,f[N],x,y,a[N],bz[N],d[N*3],ans=0;
ll max(ll x,ll y){return x>y?x:y;}
I main(){
	freopen("sequence.in","r",stdin);
	freopen("sequence.out","w",stdout);
	scanf("%lld",&n);
	F(i,1,n) scanf("%lld",&a[i]);
	if(n==2){
		printf("%lld",a[1]*a[2]-a[1]-a[2]);
		return 0;
	}
	mem(f,127);
	d[1]=0;
	f[0]=0;
	I i=1,j=1;
	while(i<=j){
		x=d[i++];bz[x]=0;
		F(k,2,n){
			y=(x+a[k])%a[1];
			if(f[y]>f[x]+a[k]){
				f[y]=f[x]+a[k];
				if(!bz[y]){
					bz[y]=1;
					d[++j]=y;
				}
			}
		}
	}
	F(i,1,a[1]-1) ans=max(ans,f[i]);
	printf("%lld\n",ans-a[1]);
	return 0;
}
           

作者：zsjzliziyang 

QQ:1634151125 

轉載及修改請注明 

本文位址:https://blog.csdn.net/zsjzliziyang/article/details/99609192