ACboy needs your help
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3026 Accepted Submission(s): 1565
Problem Description
ACboy has N courses this term, and he plans to spend at most M days on study.Of course,the profit he will gain from different course depending on the days he spend on it.How to arrange the M days for the N courses to maximize the profit?
Input
The input consists of multiple data sets. A data set starts with a line containing two positive integers N and M, N is the number of courses, M is the days ACboy has.
Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j].
N = 0 and M = 0 ends the input.
Next follow a matrix A[i][j], (1<=i<=N<=100,1<=j<=M<=100).A[i][j] indicates if ACboy spend j days on ith course he will get profit of value A[i][j].
N = 0 and M = 0 ends the input.
Output
For each data set, your program should output a line which contains the number of the max profit ACboy will gain.
Sample Input
2 2 1 2 1 3 2 2 2 1 2 1 2 3 3 2 1 3 2 1 0 0
Sample Output
3 4 6
Source
Recommend
lcy
简单的分组背包
#include <cstdio> #include <cmath> #include <algorithm> #include <iostream> #include <cstring> #include <map> #include <string> #include <stack> #include <cctype> #include <vector> #include <queue> #include <set> #include <utility> using namespace std; //#define Online_Judge #define outstars cout << "***********************" << endl; #define clr(a,b) memset(a,b,sizeof(a)) #define lson l , mid , rt << 1 #define rson mid + 1 , r , rt << 1 | 1 #define mk make_pair #define FOR(i , x , n) for(int i = (x) ; i < (n) ; i++) #define FORR(i , x , n) for(int i = (x) ; i <= (n) ; i++) #define REP(i , x , n) for(int i = (x) ; i > (n) ; i--) #define REPP(i ,x , n) for(int i = (x) ; i >= (n) ; i--) const int MAXN = 100 + 50; const long long LLMAX = 0x7fffffffffffffffLL; const long long LLMIN = 0x8000000000000000LL; const int INF = 0x7fffffff; const int IMIN = 0x80000000; #define eps 1e-8 #define mod 1000000007 typedef long long LL; const double PI = acos(-1.0); typedef double D; typedef pair<int , int> pi; ///#pragma comment(linker, "/STACK:102400000,102400000") int a[MAXN][MAXN]; int dp[MAXN]; int main() { //ios::sync_with_stdio(false); #ifdef Online_Judge freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif // Online_Judge int n , m ; while(~scanf("%d%d" , &n , &m) , (n || m)) { FORR(i , 1, n)FORR(j , 1 , m)scanf("%d" , &a[i][j]); clr(dp , 0); FORR(i , 1, n)REPP(j , m , 0)FORR(k , 1 , j)dp[j] = max(dp[j] , dp[j - k] + a[i][k]); printf("%d\n" ,dp[m]); } return 0; }