Piggy-Bank HDU 1114
初始化的细节问题：
因为要求恰好装满！！
所以初始化要注意：
初始化时除了F[0]为0，其它F[1..V]均设为−∞。
又这个题目是求最小价值：
则就是初始化时除了F[0]为0，其它F[1..V]均设为∞。
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int inf=1000005;
int a[],b[],dp[];
int main()
{
int t,n,n1,m,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&n1);
n=n1-n;
scanf("%d",&m);
for(i=;i<m;i++)
scanf("%d%d",&a[i],&b[i]);
memset(dp,inf,sizeof(dp));
dp[]=;
for(i=;i<m;i++)
for(j=b[i];j<=n;j++)
dp[j]=min(dp[j],dp[j-b[i]]+a[i]);
if(dp[n]<=inf)
printf("The minimum amount of money in the piggy-bank is %d.\n",dp[n]);
else
printf("This is impossible.\n");
}
return ;
}
还有：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int inf=1000005;
int a[],b[],dp[];
int main()
{
int t,n,n1,m,i,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&n1);
n=n1-n;
scanf("%d",&m);
for(i=;i<m;i++)
scanf("%d%d",&a[i],&b[i]);
for(i=1;i<=n;i++)
dp[i]=inf;
dp[]=;
for(i=;i<m;i++)
for(j=b[i];j<=n;j++)
dp[j]=min(dp[j],dp[j-b[i]]+a[i]);
if(dp[n]!=inf)
printf("The minimum amount of money in the piggy-bank is %d.\n",dp[n]);
else
printf("This is impossible.\n");
}
return ;
}