题意：一个人想买手表，给你n个价值的硬币，然后给你n个价值硬币对应的个数、但是呢，这个人只知道这个手表的价格不超过m元、问他最多能买多少种价值的手表
思路：dp背包专题 但是- - 一直不知道该怎么dp 终于想通了、
PS：对于背包dp说一说自己的理解吧（虽然不知道有什么用） 一旦涉及到dp 你就要考虑dp数组里面存的是什么，另外一维数组的话你就要考虑dp[i]中，那个i代表的是什么，同理二维数组也是一样、 然后写出状态转移方程，你的状态转移方程一定要和你dp数组里面存的状态是相一致的、
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int qq=;
int a[qq],c[qq];
int dp[]; //dp[i]代表价值为i能用硬币的最大数量、
int m;
void wanquan(int x,int y)
{
for(int i=x*y;i<=m;++i)
if(dp[i-x])
dp[i]=max(dp[i],dp[i-x]+y);
else if(i-x==)
dp[i]=max(dp[i],dp[i-x]+y);
return;
}
void beibao(int x,int y)
{
int c=x*y;
for(int i=m;i>=c;--i)
if(dp[i-c])
dp[i]=max(dp[i],dp[i-c]+y);
else if(i-c==)
dp[i]=max(dp[i],dp[i-x]+y);
}
void f(int x,int y)
{
if(x*y>=m){
wanquan(x,);
return;
}
int t=;
while(y>=t){
beibao(x,t);
y=y-t;
t=t<<;
}
if(y) beibao(x,y);
}
int main()
{
int n;
while(~scanf("%d%d",&n,&m)&&(n||m)){
memset(dp,,sizeof(dp));
for(int i=;i<n;++i)
scanf("%d",&a[i]);
for(int i=;i<n;++i)
scanf("%d",&c[i]);
int count=;
for(int i=;i<n;++i)
f(a[i],c[i]);
int sum=;
// for(int i=1;i<=m;++i)
// printf("%d ",dp[i]);
for(int i=;i<=m;++i) //dp[i]不为0也就是说能用所拥有的硬币组成价值i
if(dp[i]) ++sum;
printf("%d\n",sum);
}
return ;
}
去杭州前把这道题A了 没来得及记录下、 今天补上