CF10E Greedy Change

链接

( ext{明显的恶意评分好吧})

Idea

题目中说了，一种(DP)，一种贪心；

我用的贪心

Solution

设找零钱的最小表示为(f(x))，贪心表示为(G(x))，最小不满足(f(x)=G(x))的值为(w)。

如题中，(f(6)={0,2,0}),(G(6)={1,0,2})。

设(f(w))第一个非(0)元素在位置(i)，最后一个非(0)元素在位置(j)

有这么一个结论：

(f(w))和(G(a[i-1]-1))从(1)到(j-1)位都相等，(f[j]=G[j]+1)。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>
#define ll long long
#define maxn 550
#define inf 2147483647
#define mod 10003
#define eps 1e-6
#define pi acos(-1.0)
#define de(x) ((x)*(x))
using namespace std; 
inline int read(){
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int a[maxn];
int ans=inf,n;
inline int G(int x){
	int ans=0;
	for(int i=1;i<=n;i++){
		int d=x/a[i];
		ans+=d;
		x-=a[i]*d;	
	}
	return ans;
}
signed main(){
	n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=2;i<=n;i++){
    	int x=a[i-1]-1;
    	int y=x,sum=0;
    	for(int j=1;j<=n;j++){
    		int d=x/a[j];
    		sum+=d;
    		x-=a[j]*d;
    		if(sum+1<G(y-x+a[j])) ans=min(ans,y-x+a[j]);
		}
	}
	if(ans==inf) puts("-1");
	else printf("%d",ans); 
    return 0;
}