/****************************************\
* Author : ztx
* Title  : [国家集训队2000]叠放箱子
* ALG    : dp
* CMT    :
* Time   :
\****************************************/

/****************************************\
* Author : ztx
* Title  : [国家集训队2000]叠放箱子
* ALG    : dp
* CMT    :
* Time   :
\****************************************/

#include <cstdio>

int CH ;
inline void read(int& ret) {
    ret = 0 ; while (CH=getchar() , CH<'!') ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
}

#define  maxn  1010LL
#define  maxw  6010LL

int n , ans = 0 , answ = 0 , wei[maxn] , lim[maxn] ;
int f[maxn][maxw] = {0} ;
int pre[maxn][maxw] = {0} ;

void PrintfPath(int now , int w) {
	if (now>n || w<=0) return ;
	PrintfPath(now+1 , pre[now][w]) ;
	if (pre[now][w] != w) printf("%d\n",now) ;
}

int i , w ;
int main() {
	#define READ
	#ifdef  READ
		freopen("boxes.in" ,"r",stdin ) ;
		freopen("boxes.out","w",stdout) ;
	#endif
	read(n) ;
	for (i = 1 ; i <= n ; i ++ ) {
		read(wei[i]) , read(lim[i]) ;
		f[i][wei[i]] = 1 ;
	}
	for (i = n ; i > 0 ; i -- )
		for (w = 6000 ; w > 0 ; w -- ) {
			f[i][w] = f[i+1][w] ;
			pre[i][w] = w ;
			if (w<=lim[i] && f[i][w+wei[i]]<f[i+1][w]+1) {
				f[i][w+wei[i]] = f[i+1][w]+1 ;
				pre[i][w+wei[i]] = w ;
			}
		}
	for (w = 6000 ; w > 0 ; w -- )
		if (f[1][w] > ans) ans = f[1][w] , answ = w ;
	printf("%d\n", ans );
	PrintfPath(1 , answ) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}

• 相关文章
• 全局相关文章