D - Strange Lunchbox

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 ;
}
上一篇:B. Strange Definition 题解(质因子分解+思维)


下一篇:CF1558F Strange Sort