BZOJ3233 [Ahoi 2013] 동전 찾기(선형 체 + dp)

[문제풀이]
본연은 줄곧 2차원 dp를 생각하고 있었는데, 문제풀이를 보고서야 1차원으로 f[i]를 최대 액면가가 i로 설정할 수 있다는 것을 발견했을 때, 모든 토끼종이를 사서 쓴 최소 동전의 수를
f[i]=min {f[j]-sigma(a[k]/i*(i/j-1)}, j|i, 그 중에서 j는 차대면값이다. 이 방정식은 i를 선택하면 j의 사용을 얼마나 줄일 수 있는지를 고려한다.
주의,
만약 동전의 종류가 매우 많다면, 가장 좋은 답안에 영향을 주지 않을 것이다(쓰지 않으면 된다)----------->중요한 성질
따라서 j를 매거하는 이 단계에서 최적화할 수 있다.
i/j는 반드시 질수로 규정해야 한다. 그렇지 않으면 그것들 사이에 액면가 k를 추가하여 i/k, k/j가 모두 질수로 답안에 영향을 주지 않도록 할 수 있다.
온라인으로 체질하는 과정에서 수조min[i]:i의 최소 질인자를 구할 수 있다. 이를 통해 i만 매거할 수 있다.
질인자는 i/j의 값으로 한다
n의 질량 인자 개수는 log(n) 레벨이고 복잡도: O(n*Max*log(Max)
【코드】

#include<stdio.h>
#include<stdlib.h>
int a[100005],f[100005],pri[100005],min[100005];
int main()
{
	int n,i,j,k,Ma=0,cnt=0,t,ans;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		f[1]+=a[i];
		if(Ma<a[i]) Ma=a[i];
	}
	for(i=2;i<=Ma;i++)
	{
		if(min[i]==0)
		{
			pri[++cnt]=i;
			min[i]=i;
		}
		for(j=1;j<=cnt&&pri[j]*i<=Ma;j++)
		{
			min[pri[j]*i]=pri[j];
			if(i%pri[j]==0) break;
		}
	}
	for(i=2;i<=Ma;i++)
		f[i]=f[1];
	ans=f[1];
	for(i=2;i<=Ma;i++)
	{
		j=i;
		while(j>1)
		{
			t=f[i/min[j]];
			for(k=1;k<=n;k++)
				t-=a[k]/i*(min[j]-1);
			if(f[i]>t) f[i]=t;
			while(min[j]==min[j/min[j]]) j/=min[j];
			j/=min[j];
		}
		if(ans>f[i]) ans=f[i];
	}
	printf("%d",ans);
	return 0;
}