SHARE
TWEET

Untitled

a guest Nov 15th, 2019 91 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Рюкзак
  2. ------------------------
  3. dp[i][w], i - индекс объекта, w - набранный вес
  4. dp[0][w]=0
  5.  
  6. dp[i][w] = max(dp[i-1][w],dp[i-1][w-w_i]+c+1)
  7.                      ^        ^
  8.               не взяли        i-й взяли
  9.  
  10. ====================================
  11.  
  12. vector <int> w,c;
  13. int W, n;
  14. vector<int> prev(w+1);
  15. vector<int> cur(w+1);
  16. vector <vector <int>> dp(n+1, vector<int> (w+1));
  17. for(int i=1; i<=n; ++i) {
  18.   for(int j=w[i-1]; j<=w; ++j) cur[j] = max(prev[j], prev[j-w[i-1]+c[i-1]);
  19.   for(int j=0; j<w[i-1];++j) cur[j]=prev[j];
  20.   prev.swap(cur);
  21. }
  22.  
  23. |||||||||||
  24. LCS
  25. -------------
  26. A[1..n]
  27. B[1..m]
  28. LCS(An,Bm)=max(if A[n]=B[m] LCS(An-1,Bm-1)+1; else ? LCS(A_n, B_m-1) : LCS(A_n-1, B_m))
  29. ==============================
  30. string a,b;
  31. int n,m;
  32. vector<vector <int>> dp(n+1, vector<int>(m+1));
  33. for(int i=1;i<=n;++i) {
  34.   for(int j=1;j!=m;++j) {
  35.     if(a[i-1]==b[j-1]) {
  36.       dp[i][j]=dp[i-1][j-1]+1;
  37.     }
  38.     dp[i][j]=max(dp[i][j],max(dp[i-1][j],dp[i][j-1]));
  39.   }
  40. }
  41.  
  42. |||||||||||||||||
  43. MultiMatrix
  44. ----------------------
  45. n - количество матриц
  46. row-строки; с-столбцы
  47. dp[l][r]=min(dp[l][k]+dp[k+1][r]+row[l]*c[l]*c[k]);
  48.           ^
  49.          l<=k<r
  50. dp[1][1]=0;
  51. ==========================
  52. int dp(int l, int r, vector<vector <int>>& memo) {
  53.   if(l==r) return 0;
  54.   int result=dp(l, l, memo)+dp(l+1, r, memo)+rows[l]*cols[r]*cols[l];
  55.   for(int k=l+1;k<r;++i) {
  56.     result =min(result, dp(l,k,memo)+dp(k+1,r,memo)+rows[l]*cols[r]*cols[k]);
  57.   }
  58.   memo[l][r]=result;
  59.   return result;
  60. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top