D - Strange Lunchbox
链接
(好久不写dp题了,都快忘没了)
状态f[n][m] n为a的大小, m为b的大小,要求最小的个数 f[x][y] = f[x][y] = min(f[x][y] , f[max(0 , x - a[i])][max(0 , y - b[i] )] + 1 ) ;
#include <bits/stdc++.h>
using namespace std;
const int N = 310;
int a[N] , b[N] ;
int f[N][N] ;
int n , X , Y, x , y ;
int main()
{
cin>>n;
cin>>X>>Y;
for(int i = 1 ; i <= n ; i ++ )
{
cin>>a[i] >>b[i ] ;
}
memset(f , 0x3f , sizeof f ) ;
f[0][0] = 0 ;
for(int i = 1 ; i <= n ; i ++)
{
for(int x = X; x >= 0 ; x -- )
{
for(int y = Y ; y >= 0 ; y --)
{
f[x][y] = min(f[x][y] , f[max(0 , x - a[i])][max(0 , y - b[i] )] + 1 ) ;
}
}
}
if(f[X][Y] == 0x3f3f3f3f) f[X][Y] = -1 ;
cout<<f[X][Y] ;
return 0 ;
}