头像

yaleyaledaze




离线:3天前



yaleyaledaze
2个月前

二分查找部分非常灵活,这里直接使用STL自带的二分查找算法。

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    int len = 0;
    for (int i = 0; i < n; i++)
    {
        int  pos = len;
        pos = lower_bound(q + 1, q + len + 1, a[i]) - (q + 1);
        len = max(len, pos + 1);
        q[pos + 1] = a[i];
    }

    cout << len << endl;

    return 0;
}

关于此题的二分查找,参考一下@well188的评论:
二分就是太灵活了,太容易出错了,想不出错就得像STL那样,范围永远:“左闭右开”,检查条件永远:“大于等于或大于”。不得不承认,有时候加上限制反而更敏捷。

int len=0;
q[0]=-1e9;//因为有负值,第0个数还是要设一个最小值
for(int i=0;i<n;i++){
    int l=0,r=len+1;//左闭右开
    while(l<r){
        int mid=l+r>>1;
        if(q[mid]>=a[i]) r=mid;
        else l=mid+1;
    }
    len=max(len,l);//这里r和l都可以,因为左闭右开保证能进入while循环
    q[l]=a[i];
}
printf("%d\n",len);

作者:well188
链接:https://www.acwing.com/activity/content/code/content/62458/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。




yaleyaledaze
2个月前
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100010;

int n;
int a[N];
int q[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    int len = 0;
    for (int i = 0; i < n; i++)
    {
        int  pos = len;
        pos = lower_bound(q + 1, q + len + 1, a[i]) - (q + 1);
        len = max(len, pos + 1);
        q[pos + 1] = a[i];
    }

    cout << len << endl;


    return 0;
}


活动打卡代码 AcWing 282. 石子合并

yaleyaledaze
2个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 310;

int n;
int s[N];
int f[N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];

    for (int i = 1; i <= n; i++)
        s[i] += s[i - 1];

    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int l = i, r = i + len - 1;
            f[l][r] = 1e9;
            for (int k = l; k < r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }

    cout << f[1][n] << endl;
    return 0;
}



yaleyaledaze
3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int f[N][N];
char a[N], b[N];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if (a[i] == b[j])
                f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    cout << f[n][m] << endl;
    return 0;
}



yaleyaledaze
3个月前

题目描述

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

样例

input:
3 5
2
1 2
2 4
1
3 4
1
4 5
output:
8

C++ 代码

显然状态转移方程为

f[i,j]=max(f[i-1][j],f[i-1,j-v[i,k]]+w[i,k])

其实这个状态转移方程只是粗略的,有很多问题。

依照这个方程粗略地写出代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int f[N][N], s[N], v[N][N], w[N][N];

int main()
{
    int m, n;
    cin >> m >> n; //m=N,n=V

    for (int i = 1; i <= m; i++)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= m; i++)
        for (int j = 0; j <= n; j++)
            for (int k = 1; k <= s[i] && j >= v[i][k]; k++)
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i][k]] + w[i][k]);
    cout << f[m][n] << endl;
    return 0;
}

wa了个痛快!

那么错在哪里呢?

首先让我们写出正确的代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int f[N][N], s[N], v[N][N], w[N][N];

int main()
{
    int m, n;
    cin >> m >> n; //m=N,n=V

    for (int i = 1; i <= m; i++)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= m; i++)
        for (int j = 0; j <= n; j++)
            for (int k = 1; k <= s[i]; k++){
                f[i][j] = max(f[i-1][j], f[i][j]);
                if(j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
            }
    cout << f[m][n] << endl;
    return 0;
}

首先是循环体的K的条件,

for(int k=0;k<=s[i]&&v[i][k]<=j;k++)

这么写有什么问题呢?

v[i] [k]关于k并不是递增的,所以当前的k不满足要求,并不意味着后面的k也不满足要求,不能结束循环,应该改成:

if(j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);

还有一个小细节!那就是

f[i][j] = max(f[i-1][j], f[i][j]);

因为有可能这一层一个也放不下,但是你不这么写的话那么当前层就为0,而实际应该更新为上一层的值才对。

不得不说压缩成一维才是真的香!!!
我们看一维的

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int f[N], s[N], v[N][N], w[N][N];

int main()
{
    int m, n;
    cin >> m >> n; //m=N,n=V

    for (int i = 1; i <= m; i++)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= m; i++)
        for (int j = n; j >= 0; j--)
            for (int k = 1; k <= s[i]; k++){
                //f[i][j] = max(f[i-1][j], f[i][j]);
                if(j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
            }
    cout << f[n] << endl;
    return 0;
}

注意一下这里注释的地方,删掉了一维就是恒等式了,所以可以省略不写,但写二维的时候一定要写




yaleyaledaze
3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int a[N], f[N];

int main()
{
    int n, res = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for (int j = 1; j < i; j++)
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }

    cout << res << endl;
    return 0;
}


活动打卡代码 AcWing 898. 数字三角形

yaleyaledaze
3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 510;
int a[N][N];

int main()
{
    int n, ans = 0;
    cin >> n;
    memset(a,-0x37,sizeof(a));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];

    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++)
            a[i][j] += max(a[i - 1][j - 1], a[i - 1][j]);
    for (int i = 1; i <= n;i++)
        ans = max(ans, a[n][i]);
    cout << ans << endl;
    //system("pause");
    return 0;
}



yaleyaledaze
3个月前

显然状态转移方程为

f[i,j]=max(f[i-1][j],f[i-1,j-v[i,k]]+w[i,k])

其实这个状态转移方程只是粗略的,有很多问题。

依照这个方程粗略地写出代码

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int f[N][N], s[N], v[N][N], w[N][N];

int main()
{
    int m, n;
    cin >> m >> n; //m=N,n=V

    for (int i = 1; i <= m; i++)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= m; i++)
        for (int j = 0; j <= n; j++)
            for (int k = 1; k <= s[i] && j >= v[i][k]; k++)
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i][k]] + w[i][k]);
    cout << f[m][n] << endl;
    return 0;
}

wa了个痛快!

那么错在哪里呢?

首先让我们写出正确的代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int f[N][N], s[N], v[N][N], w[N][N];

int main()
{
    int m, n;
    cin >> m >> n; //m=N,n=V

    for (int i = 1; i <= m; i++)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= m; i++)
        for (int j = 0; j <= n; j++)
            for (int k = 1; k <= s[i]; k++){
                f[i][j] = max(f[i-1][j], f[i][j]);
                if(j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
            }
    cout << f[m][n] << endl;
    return 0;
}

首先是循环体的K的条件,

for(int k=0;k<=s[i]&&v[i][k]<=j;k++)

这么写有什么问题呢?

v[i] [k]关于k并不是递增的,所以当前的k不满足要求,并不意味着后面的k也不满足要求,不能结束循环,应该改成:

if(j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);

还有一个小细节!那就是

f[i][j] = max(f[i-1][j], f[i][j]);

因为有可能这一层一个也放不下,但是你不这么写的话那么当前层就为0,而实际应该更新为上一层的值才对。

不得不说压缩成一维才是真的香!!!
我们看一维的

#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int f[N], s[N], v[N][N], w[N][N];

int main()
{
    int m, n;
    cin >> m >> n; //m=N,n=V

    for (int i = 1; i <= m; i++)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= m; i++)
        for (int j = n; j >= 0; j--)
            for (int k = 1; k <= s[i]; k++){
                //f[i][j] = max(f[i-1][j], f[i][j]);
                if(j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
            }
    cout << f[n] << endl;
    return 0;
}

注意一下这里注释的地方,删掉了一维就是恒等式了,所以可以省略不写,但写二维的时候一定要写



活动打卡代码 AcWing 9. 分组背包问题

yaleyaledaze
3个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 110;
int f[N][N], s[N], v[N][N], w[N][N];

int main()
{
    int m, n;
    cin >> m >> n; //m=N,n=V

    for (int i = 1; i <= m; i++)
    {
        cin >> s[i];
        for (int j = 1; j <= s[i]; j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1; i <= m; i++)
        for (int j = 0; j <= n; j++)
            for (int k = 1; k <= s[i]; k++){
                f[i][j] = max(f[i-1][j], f[i][j]);
                if(j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
            }
    cout << f[m][n] << endl;
    return 0;
}


活动打卡代码 AcWing 5. 多重背包问题 II

yaleyaledaze
3个月前
#include <bits/stdc++.h>

using namespace std;

const int N = 12010, M = 2010;

int n, m;
int v[N], w[N];
int f[M];

int main()
{
    cin >> n >> m;

    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        int a, b, s;  //体积  权重  个数
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s)
        {
            cnt ++ ;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s > 0)   //剩余部分
        {
            cnt ++ ;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }

    n = cnt;

    for (int i = 1; i <= n; i ++ )    //01背包
        for (int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    //system("pause");

    return 0;
}