标签：return CF889E int 题解 second getchar mod

题目描述

\[f(x,n) = x \mod a_n \]

\[f(x,i) = ( x \mod a_i ) + f(x \mod a_i,i+1) \]

给出a序列，当x取遍所有非负整数时\(f(x,1)\)的最大值。

题解

首先注意到\(a_i\)只有比前面所有的\(a\)都小时才有用废话
其次是\(x\)的规模每次都会缩到\(a_i\)的同余系内。
然后似乎就没有思路了（悲
实际上，注意到在最优方案种一定存在某时刻\(x=a_i-1\)，否则我们可以将\(x\)加一使得答案变大。
那么我们对于一个\(x\)就有两种操作：

• 保持x不加减，模\(a_i\)
• 使得x模之后变为 \(a_i-1\)

由此设计DP,\(f[i][j]\)为到第i个a时当前答案是\(i\times j+f[i][j]\)的最大值。
转移如下：

\[f(i+1,j\bmod a_{i+1}) = f(i,j) + (j-j\bmod a_{i+1})*i\\ f(i+1,a_{i+1}-1) = f(i,j) + ((j+1)/a_{i+1}*a_{i+1}-a_{i+1})*i \]

第二种转移是减是因为加我们并清楚对于之前的\(a\)的影响是什么，而减一定不会影响之前的。

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd(){
	int f=1,j=0;
	char w=getchar();
	while(!isdigit(w)){
		if(w=='-')f=-1;
		w=getchar();
	}
	while(isdigit(w)){
		j=j*10+w-'0';
		w=getchar();
	}
	return f*j;
}
const int N=200010;
int n,a[N],ans;
map<int,int>f;
signed main(){
	n=rd();
	for(int i=1;i<=n;i++)a[i]=rd();
	f[a[1]-1]=0;
	for(int i=2;i<=n;i++){
		for(auto it=f.lower_bound(a[i]);it!=f.end();it++){
//			cout<<"kkk\n";
			int x=it->first,y=it->second;
//			cout<<x<<":"<<y<<"\n";
			f[x%a[i]]=max(f[x%a[i]],y+(i-1)*(x-x%a[i]));
			f[a[i]-1]=max(f[a[i]-1],y+(i-1)*((x+1)/a[i]*a[i]-a[i])); 
		}
		while(true){
			auto it=f.lower_bound(a[i]);
			if(it==f.end())break;
			f.erase(it);
		}
	}
	for(auto it=f.begin();it!=f.end();it++){
//		cout<<it->first<<":"<<it->second<<"\n";
		ans=max(ans,n*(it->first)+(it->second));
	}
	printf("%lld\n",ans);
	return 0;
}

标签：return,CF889E,int,题解,second,getchar,mod
From： https://www.cnblogs.com/T-water/p/17236732.html