@[caojiaming](/user/775551) 不用记忆化也能过
by da_ke @ 2023-05-16 22:36:11
我也是记忆化搜索，50pts
```c
#include <stdio.h>
#define max(a,b) (a)>(b)?(a):(b)
long long v[28],p[28],mem[28][30001];
long long dp(int x,int s)
{
if(mem[x][s]!=0) return mem[x][s];
if(x==0)
{
if(v[0]>s)
{
return 0;
}
return v[0]*p[0];
}
if(v[x]>s)
{
mem[x-1][s]=dp(x-1,s);
return mem[x-1][s];
}
if(mem[x-1][s-v[x]]==0) mem[x-1][s-v[x]]=v[x]*p[x]+dp(x-1,s-v[x]);
if(mem[x-1][s]==0) mem[x-1][s]=dp(x-1,s);
return max(mem[x-1][s-v[x]],mem[x-1][s]);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%lld%lld",&v[i],&p[i]);
}
printf("%lld\n",dp(m-1,n));
return 0;
}
```
一起求调
by Jianbing_Juan @ 2023-07-07 01:03:34
@[Jianbing_Juan](/user/940854)
这题用大暴搜似乎也能过
```cpp
#include<iostream>
using namespace std;
int n,m,v[30],p[30],ans;
void search(int money,int k,int nans) {
if(money>n)
return;
if(k==m+1) {
ans=max(ans,nans);
return;
}
search(money,k+1,nans);
search(money+v[k],k+1,nans+v[k]*p[k]);
}
int main() {
cin>>n>>m;
for(int i=1; i<=m; i++)
cin>>v[i]>>p[i];
search(0,1,0);
cout<<ans<<endl;
return 0;
}
```
by awawawawa @ 2023-08-20 15:30:25
@[awawawawa](/user/753880) 这个题我已经过了，dp用函数递归的话转移应该容易挂。后来我改循环了
by Jianbing_Juan @ 2023-08-21 00:02:23