01背包34分求助!
查看原帖
01背包34分求助!
950927
_luo_gu楼主2023/11/1 21:12

本蒟蒻的思路是先dp怎样在时间尽量少的情况下使作业的分数及格,然后再用剩余的时间全部用来刷题。 代码:

/*
	dp怎样快速使作业及格 
	然后sort题目输出 
*/
#include <bits/stdc++.h>
using namespace std ;
int n , m , k , r , dp[60] , q_time[60] , c[60] , v[60] , timee , cnt ;  
signed main(){
	scanf("%d %d %d %d\n" , &n , &m , &k , &r );
	for( int i = 1 ; i <= n ; i ++ ){
		scanf("%d " , &q_time[i] );
	}
	for( int i = 1 ; i <= n ; i ++ ){
		scanf("%d " , &c[i] );
	}
	for( int i = 1 ; i <= n ; i ++ ){
		scanf("%d " , &v[i] );
	}
	sort(q_time + 1 , q_time + n + 1 );
	timee = 2147483647 ;
	for( int i = 1 ; i <= m ; i ++ ){
		for( int j = r ; j >= c[i] ; j -- ){
			dp[j] = max( dp[j] , dp[j - c[i]] + v[i] ) ;
			if( dp[j] >= k ){
				timee = min( timee , j );
			}
		}
	}
	int i = 1 ;
	int t = timee ;
	while( true ){
		if( t + q_time[i] > r ){
			break ;
		}
		t += q_time[i] ;
		i ++ ;
	}
	cout << i  << endl;
	return 0 ;
}

但是这个代码一直只有34分,不知道为啥,自己看起来好像没啥问题。

感谢大佬!

2023/11/1 21:12
加载中...