uva 10306 e-coins【dp】

二维完全背包

#include <bits/stdc++.h>
#define cl(a) memset(a,0,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=b;i>=a;i--)
#define sc(x) scanf("%d",&x)
#define fi first
#define se second
using namespace std;
const int mod=1e9+7;
typedef long long ll;
const int maxn=1e5+50;
const int inf=0x3f3f3f3f;
typedef pair<int,int>PII;
ll fpow(ll n,ll k,ll p=mod){ll r=1;for(;k;k>>=1){if(k&1)r=r*n%p;n=n*n%p;}return r;}
ll inv(ll n,ll p=mod){return fpow(n,p-2,p);}
ll fact[maxn];
void init(ll p = mod){fact[0]=1;rep(i,1,maxn-1)fact[i]=fact[i-1]*i%p;}
ll C(ll n,ll m,ll p=mod){return fact[n]*inv(fact[m])%p*inv(fact[n-m])%p;}
struct node
{
    int x,y;
};
node a[105];
int n,m,s;
int dp[350][350];
int main()
{
    sc(n);
    while(n--)
    {
        sc(m);sc(s);
        rep(i,1,m){sc(a[i].x);sc(a[i].y);}
        memset(dp,inf,sizeof(dp));
        dp[0][0]=0;
        int ans=inf;
        for(int i=0;i<=s;i++)
        {
            for(int j=0;j<=s;j++)
            {
                rep(k,1,m) if((i-a[k].x>=0)&&(j-a[k].y>=0))dp[i][j] = min(dp[i][j],dp[i-a[k].x][j-a[k].y]+1);
                if((i*i+j*j)==s*s) ans = min(ans,dp[i][j]);
                //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
            }
        }
        if(ans==inf)printf("not possible\n");
        else
        printf("%d\n",ans);
    }
    return 0;

}