• API
• FAQ
• Tools
• Archive
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.

Top