第一次测试的最后一道题...
本来信心满满可以过的然后几乎全WA...
下午一检查
全!是!错!
难受死了www
暗黑破坏神(diablo.pas)无聊中的小 x 玩起了 Diablo I...游戏的主人公有 n 个魔法每个魔法分为若干个等级,第 i 个魔法有 p[i]个等级(不包括 0)每个魔法的每个等级都有一个效果值,一个 j 级的 i 种魔法的效果值为 w[i][j]魔法升一级需要一本相应的魔法书购买魔法书需要金币,第 i 个魔法的魔法书价格为 c[i]而小 x 只有 m 个金币(好孩子不用修改器)你的任务就是帮助小 x 决定如何购买魔法书才能使所有魔法的效果值之和最大开始时所有魔法为 0 级 效果值为 0输入(diablo.in) 第一行 用空格隔开的两个整数 n m 以下 n 行 描述 n 个魔法 第 i+1 行描述 第 i 个魔法 格式如下 c[i] p[i] w[i][1] w[i][2] ... w[i][p[i]]输出(diablo.out) 第一行输出一个整数,即最大效果值。 以后 n 行输出你的方案: 第 i+1 行有一个整数 v[i] 表示你决定把第 i 个魔法学到 v[i]级 如果有多解 输出花费金币最少的一组 如果还多解 输出任意一组样例
Input | Output |
3 101 3 1 2 22 3 2 4 63 3 2 1 10 | 111 0 3 |
约定0<n<=1000<m<=5000<p[i]<=500<c[i]<=10保证输入数据和最终结果在 longint 范围内
1 #include2 using namespace std; 3 4 int n , m ; 5 int c[601] , p[601] , w[601][601] , f[601][501]; 6 int shu[601] ; 7 8 int get(){ 9 char c ;10 int symple = 1 ;11 while((c = getchar())<'0'||c > '9')12 if(c == '-') symple = -1 ;13 int ans = c - '0' ;14 while((c = getchar())>='0'&&c <='9')15 ans = ans * 10 + c - '0' ;16 return ans * symple ; 17 }18 19 int main(){20 //freopen("diablo.in","r",stdin);21 //freopen("diablo.out","w",stdout);22 n = get() , m = get() ;23 for(int i = 1 ; i <= n ; ++ i){24 c[i] = get() , p[i] = get() ;25 for(int j = 1 ; j <= p[i] ; ++ j){26 w[i][j] = get();27 }28 }29 30 for(int i = 1 ; i <= n ; ++ i)31 for(int k = p[i] ; k >= 0 ; -- k){ 32 // 你是笨蛋吗???一定要记得倒序啊啊啊啊啊!!!!不要再像白痴一样查一个错查一下午了啊啊啊啊啊啊!!!33 for(int j = m ; j >= k * c[i] ; -- j){34 f[i][j] = max(f[i][j] , f[i - 1][j - k * c[i]] + w[i][k]);35 }36 }37 cout << f[n][m] < = 1 ; -- i){41 //输出跟标程的方法不一样...42 //然而测试的时候连输出都没写对... (划掉划掉) 43 //我不管反正我的简单多了 (‘▽′)Ψ44 for(int j = 0 ; j <= p[i] ; ++ j){45 46 shu[i] = j ;47 yu -= j*c[i] ;48 f[n][m] -= w[i][j] ;49 break ;50 }51 }52 }53 for(int i = 1 ; i <= n ; ++ i)54 cout < <