LIS最長遞增子序列

int dp[MAXN], arr[MAXN];
vector <int > v;
for(int i = 1;i <= n;i++) {
    int idx = lower_bound (v. begin () , v.end () , arr[i]) - v.begin ();
    dp[i] = idx + 1;
    if(idx == v.size ()) v. push_back (arr[i]);
    else v[idx] = arr[i];
}
cout << v. size () << "\n";

01背包

for(int i = 1;i <= n;i++){
    for(int j = C;j >= 0;j--){
        if(j-w[i] >= 0){
            dp[j] = max(dp[j], dp[j-w[i]] + 1);
        }
    }
}

無限背包

for(int i = 1;i <= n;i++){
    for(int j = 0;j <= C;j++){
        if(j-w[i] >= 0){
            dp[j] = max(dp[j], dp[j-w[i]] + 1);
        }
    }
}