Mr.Lee 的评测机 题解
学无止境
2018-11-20 17:51:51
本题就是签到题啦
相信大家很容易看出这是 $01$ 背包的模型，只需要在 $M $ 秒内关闭程序获得最大的价值即可，接着进行处理判断可以通过的测试点数量便可以通过本题了!
$Code:$
```
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,k,p,tmp1,tmp2,f[30010],ans;
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&p);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&tmp1,&tmp2);
for(int j=m;j>=tmp1;j--)
if(f[j-tmp1]+tmp2>f[j])
f[j]=f[j-tmp1]+tmp2;
}
for(int i=1;i<=k;i++)
{
scanf("%d%d",&tmp1,&tmp2);
if(tmp1*(f[m]+p)>=tmp2)
ans++;
}
if(ans==k)
printf("AC");
else
printf("%d",ans);
return 0;
}
```