Jobdu-1364-v字仇杀队[解题代码] | Acm之家


九度-1364-v字仇杀队[解题代码] | Acm之家
         最近玄影游侠看了一部非常好看的电影,叫做《v字仇杀队》。下面是这部电影的主角v
它想说明的一个问题就是,你现在所想的真的是你自己内心所想的吗?还是别人,社会让你这么想的?你要有自己的想法,每个人内心都有自己的准则,你没有必要按照大众的准则去想。
         v整整策划了一年炸掉英国政府的大楼来推翻独裁统治,在这期间,v遇到了一个问题:如何使用有限的炸弹来达到最大的破坏力。
         看过电影的人都知道,v最后使用自己偷偷建造的一个装满炸药的地铁直接开向国会大厦。虽然v的炸药很多,但是地铁中能装载的炸药数是有限的,因此,v就要挑选一部分炸药。如果换作你,你能在地铁有限的空间中装载挑选出来的炸药使得地铁的破坏力最大吗?

输入:
         每组测试数据可能有多组输入,对于每一组输入,
         输入的第一行包括两个整数S(1 <= S <= 1000)C(1<=C<=100)S代表地铁的总空间的大小,C代表v一共存储的炸药的个数。
         接下来的C行每行包括两个1100(包括1100)的整数,分别表示这个炸药所需要的空间以及它所能产生的破坏力。
输出:
         对于每组输入,输出只包括一行,这一行只包含一个整数,表示在地铁的有限的空间里转载选出的炸药,能产生的最大的破坏力。如果每个炸药的体积都很大,地铁的空间连一个炸药都装不下,输出0即可。
样例输入:
70 3 71 100 69 1 1 2
样例输出:
3
http://lyvxiang.blog.163.com/blog/static/189687272201111278210880/
14     while(scanf("%d%d",&S,&C)!=EOF){
15         int i;
16         for(i=1;i<=C;i++){
17             scanf("%d%d",&space[i],&force[i]);
18         }
19         memset(mat,0,sizeof(mat));
20         int j;
21         for(i=1;i<=C;i++)
22             for(j=0;j<=S;j++){
23                 if(j>=space[i])
24                     mat[i][j]=max(mat[i-1][j-space[i]]+force[i],mat[i-1][j]);
25                 else mat[i][j]=mat[i-1][j];
26             }
27         printf("%dn",mat[C][S]);
28     }

http://blog.csdn.net/wdy_yx/article/details/9815543
  1. void v(int S,int n){  
  2.     int *dp = new int[S+1];  
  3.     for(int i = 0;i<S+1;i++){  
  4.         dp[i]= 0 ;  
  5.     }  
  6.     
  7.     int space=0;  
  8.     int power=0;  
  9.     for(int i = 0;i<n;i++){  
  10.         std::cin>>space>>power;  
  11.         for(int j = S;j>=space;j--){//must decreass  
  12.             dp[j] = std::max(dp[j],dp[j-space]+power);  
  13.         }  
  14.     }  
  15.     std::cout<<dp[S]<<std::endl;  
08    while(scanf("%d %d",&c,&n) != EOF){
09        int carr[101] = { 0 }; //炸弹的空间
10        int parr[101] = { 0 }; //炸弹的威力
11        int s[1000] = { 0 }; //存储当前容量,的最大威力
12        for(int i=1; i<=n; i++)
13            scanf("%d %d",&carr[i],&parr[i]);
14        for(int i=1; i<=n; i++){
15            for(int j=c; j>0; j--){
16                int t = 0;
17                if(j >= carr[i])
18                    t = s[j-carr[i]] + parr[i];
19                s[j] = max(s[j],t);
20            }
21        }
22        printf("%d\n",s[c]);
23    }
Read full article from 九度-1364-v字仇杀队[解题代码] | Acm之家

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts