头像

回溯




离线:11小时前


最近来访(23)
用户头像
F_58
用户头像
Tilbur
用户头像
Emp
用户头像
LionBaMeng
用户头像
moreexcellent
用户头像
填海难....填心更难
用户头像
zombotany
用户头像
jyc20101031
用户头像
金伟
用户头像
睡醒继续做梦
用户头像
夏雪ζ忆梦
用户头像
影宇z
用户头像
lzs0511
用户头像
._18
用户头像
FeoBay
用户头像
a.b.c123
用户头像
虚怀


回溯
14小时前
#include <iostream>
using namespace std;

const int N = 1010;

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

//先从 n - 1倒着求一遍, 从下面往上面求, 在1 - n 判断是否选择了第i个物品

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

    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];

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

    int j = m;
    for (int i = 1; i <= n; i ++ )
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
        {
            cout << i << ' ';
            j -= v[i];
        }

    return 0;    

}



回溯
1天前
#include <iostream>
using namespace std;

/* 找规律发现, 每一次前面一项的差与后面一项的差相差12,每次差值+12, 迭代就行
    1  13  37  73 .....
     12  24  36   .....
*/

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

    int res = 1, d = 0;

    for (int i = 1; i <= n; i ++ ) res += d, d += 12;

    cout << res << endl;

    return 0;
}


活动打卡代码 AcWing 1020. 潜水员

回溯
1天前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 22 ,M = 80;

int f[N][M];
int n, m, k;

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

    memset(f, 0x3f, sizeof f);

    f[0][0] = 0;
    while (k -- )
    {
        int v1, v2, w;
        cin >> v1 >> v2 >> w;

        for (int i = n; i >= 0; i -- )
            for (int j = m; j >= 0; j -- )
                f[i][j] = min(f[i][j], f[max(0, i - v1)][max(0, j - v2)] + w);
    }

    cout << f[n][m] << endl;

    return 0;
}


活动打卡代码 AcWing 1019. 庆功会

回溯
3天前
#include <iostream>
using namespace std;

const int N = 510, M = 6010;

int f[M];
int n, m;

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

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

    cout << f[m] << endl;

    return 0;
}



回溯
3天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1010, M = 510, K = 110;

int f[N][M];

int v1, v2, n;

int main()
{
    cin >> v1 >> v2 >> n;

    for (int i = 1; i <= n; i ++ )
    {
        int v_1, v_2;
        cin >> v_1 >> v_2;

        for (int j = v1; j >= v_1; j -- )
            for (int k = v2; k >= v_2; k -- )
                f[j][k] = max(f[j][k], f[j - v_1][k - v_2] + 1);
    }

    cout << f[v1][v2 - 1] << ' ';

    int k = v2 - 1;

    while (k > 0 && f[v1][k - 1] == f[v1][v2 - 1]) k -- ;

    cout << v2 - k << endl;

    return 0;

}



回溯
5天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1010, M = 110;

int f[M][M];
int v1[N], v2[N], w[N];
int n, m, k;

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

    for (int i = 1; i <= n; i ++ ) cin >> v1[i] >> v2[i] >> w[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v1[i]; j -- )
            for (int s = k; s >= v2[i]; s -- )
                    f[j][s] = max(f[j][s], f[j - v1[i]][s - v2[i]] + w[i]);

    cout << f[m][k] << endl;

    return 0;
}



回溯
6天前
#include <iostream>
using namespace std;

int n;

int main()
{
    string str;
    cin >> str >> n;

    while (n -- )
    {
        string t = "";
        int len = str.size();
        for (int i = 0; i < len ; i ++ )
        {
            int s = 1;
            while (str[i] == str[i + 1]) s ++ , i ++ ;
            t = t + char (s + '0') + str[i];
        }

        str = t;
    }
    cout << str << endl;

    return 0;

}


活动打卡代码 AcWing 1021. 货币系统

回溯
6天前
#include <iostream>
using namespace std;

const int N = 3010;

typedef long long LL;

int v[N];
LL f[N];
int n, m;

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

    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ )
            f[j] += f[j - v[i]];

    cout << f[m] << endl;

    return 0;
}


活动打卡代码 AcWing 1021. 货币系统

回溯
6天前
#include <iostream>
using namespace std;

const int N = 3010;

typedef long long LL;

int v[N];
LL f[N];
int n, m;

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

    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ )
            f[j] += f[j - v[i]];

    cout << f[m] << endl;

    return 0;
}


活动打卡代码 AcWing 1023. 买书

回溯
6天前
#include <iostream>

using namespace std;

const int N = 1010;

int v[] = {0, 10, 20, 50, 100};
int f[N];

int m;

int main()
{
    cin >> m;

    f[0] = 1;
    for (int i = 1; i <= 4; i ++ )
        for (int j = v[i]; j <= m; j ++ )
            f[j] += f[j - v[i]];

    cout << f[m] << endl;

    return 0;

}