1276

POH1276，一道生成函数的典型模型……
题意是求用N种硬币找钱……求能找出    小于等于某个值（Cost） 的最大值
纯粹暴力：TLE
小优化：500~999MS
终极优化：0MS……

先解释一下：
Get[100010]：Boolean数组，Get[i]表示面值i能否取到

暴力：从大到小扫描，如果Get[i]=1则展开……TLE
小优化：
每次只扫描（0~前I种硬币中最大能到的面值），并展开……800MS能过
诡异的加上一个排序，将硬币从小到大排序，500MS……
外加我一个细节没处理好，常数大了点，处理好之后，300MS

终级优化：
倒着扫描，展开某个点i时，不是要把get[i+面值]，get[i+面值*2]……都赋值成1么？
这个优化是如果 get[i+面值*j]=1，就break，因为扫描时是倒着的，如果get[i+面值*j]=1，证明它肯定被展开过……后面就不用再赋值了

 

#include
#include

int a[20][2];
int b[100010];
int n,m,ans,tmp;

int main()
{
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        memset(b,0,sizeof(b));
        for (int i=1;i<=m;i++)
            scanf("%d%d",&a[i][1],&a[i][0]);
        if (n*m==0)
        {
            printf("0\n");
            continue;
        }
        b[0]=1;
        int max=0;
        for (int i=1;i<=m;i++)
        for (int j=max;j>=0;j--)
            if (b[j])
            {
                for(int k=1;k<=a[i][1];k++)
               {
     tmp = j+k*a[i][0];
     if(tmp > n || b[tmp])  break;
     if(tmp>max) max = tmp;
     b[tmp] = 1;
               }               
            }
        for (ans=n;!b[ans];ans--);
        printf("%d\n",ans);
    }
    return 0;
}