ccbeginner

UVa Q10154 (!finish)

Feb 9th, 2020
47
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //UVa Q10154
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. struct turtle{
  6.     int W, carry;
  7. }arr[5607];
  8.  
  9. int dp[5607];
  10. int weight[5607];
  11. bool cmp(turtle a, turtle b){
  12.     return a.carry < b.carry;
  13. }
  14.  
  15. int32_t main(){
  16.     int n = 0;
  17.     while(cin >> arr[n].W >> arr[n].carry)++n;
  18.     sort(arr, arr+n, cmp);
  19.     for(int i = 0; i < n; ++i)arr[i].carry -= arr[i].W;
  20.     for(int i = 0; i < n; ++i){
  21.         dp[i] = 1;
  22.         weight[i] = arr[i].W;
  23.         for(int j = 0; j < i; ++j){
  24.             if(arr[i].carry >= weight[j] && dp[i] < dp[j]+1){
  25.                 dp[i] = dp[j]+1;
  26.                 weight[i] = weight[j] + arr[i].W;
  27.             }
  28.         }
  29.     }
  30.     int big = 0;
  31.     for(int i = 1; i < n; ++i){
  32.         if(dp[big] < dp[i])big = i;
  33.     }
  34.     cout << dp[big] << '\n';
  35.     return 0;
  36. }
RAW Paste Data