#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
int a[20],num[20];
int dp[100005];
int main()
{
	int c,n,i,j,k;
	while(scanf("%d%d",&c,&n)==2)
    {
        memset(a,0,sizeof(a));
        memset(num,0,sizeof(num));
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++) scanf("%d%d",&num[i],&a[i]);
        for(i=1;i<=n;i++)
            for(j=a[i];j<=c;j++)
                for(k=1;k<=num[i];k++)
                {
                    if(j>=k*a[i])
                    {
                        dp[j]=max(dp[j],dp[j-k*a[i]]+k*a[i]);
                    }
                    else break;
                }
        printf("%d\n",dp[c]);
    }
    return 0;
}

• Re:超时代码，求指教 (814) clooszhao 2013-01-24 12:10:47