头像

whelve




离线:2小时前


最近来访(64)
用户头像
郑若辰
用户头像
qilin02811
用户头像
学算法就上acw_ing
用户头像
长小圆
用户头像
tigerchen
用户头像
离幻
用户头像
sep
用户头像
21KINGDMG
用户头像
yxc
用户头像
空号AcWing
用户头像
capper
用户头像
吃花椒的喵醤
用户头像
红色喷火龙
用户头像
朱迪
用户头像
阳青_YQ
用户头像
SKG_G
用户头像
嘉然今天不吃了
用户头像
cymzq
用户头像
LINNO
用户头像
日暮途远_25


whelve
2天前

动态规划 - 闫式DP分析法

背包问题

1、 01背包
每件物品只有两种选择,被选和不被选
f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w);
2、完全背包
每件物品都有无限件可用,朴素版做法:枚举每一个状态选取最大值,优化做法:对代码进行恒等变形得到状态转移等式

f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w, f[i - 1][j - 2v] + 2w, ... );
f[i][j - v] = max(f[i - 1][j - v], f[i - 1][j - 2v] + w, f[i - 1][j - 3v] + 2w, ... );
f[i][j] = max(f[i - 1][j], f[i][j - v] + w);

3、多重背包
由01背包转化而来,不同的是每件物品只有有限件,因此在状态转移计算中要多加一层循环,并且要判断k件物品的体积是否超过剩余体积j
for (int k = 1; k <= s && k * v <= j; k ++ );




whelve
2天前
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, M = 510;
int V1, V2, n, v1, v2;
int f[N][M];

{int main()

    cin >> V1 >> V2 >> n;
    for (int i = 0; i < n; i ++ )
    {
        cin >> v1 >> v2;
        for (int j = V1; j >= v1; j -- )
            for (int k = V2 - 1; k >= v2; k -- )
                f[j][k] = max(f[j][k], f[j - v1][k - v2] + 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;
}


活动打卡代码 AcWing 1024. 装箱问题

whelve
3天前
#include <iostream>
using namespace std;
const int N = 20005;
int n, m, v;
int f[N];

int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; i ++ )
    {
        cin >> v;
        for (int j = m; j >= v; j -- )
            f[j] = max(f[j], f[j - v] + v);
    }
    cout << m - f[m] << endl;

    return 0;
}


活动打卡代码 AcWing 423. 采药

whelve
3天前
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, v, w;
int f[N];

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

    return 0;
}


活动打卡代码 AcWing Django-6.1. 上课笔记

whelve
5天前


活动打卡代码 AcWing Django-5.1. 上课笔记

whelve
14天前



whelve
19天前
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010;
int n;
int a[N], b[N];
int f[N][N];

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


活动打卡代码 Linux Django-4.1. 上课笔记

whelve
21天前
http://139.196.8.108:8000/


活动打卡代码 Linux Django-3.1. 上课笔记

whelve
21天前
http://139.196.8.108:8000/


活动打卡代码 AcWing 823. 排列

whelve
26天前
n = int(input())
path = [0 for i in range(n)]
used = [False for i in range(n)]

def dfs(u):
    if u == n:
        for i in range(n):
            print(path[i] + 1, end = ' ')
        print()
    else:
        for i in range(n):
            if not used[i]:
                path[u] = i
                used[i] = True
                dfs(u + 1)
                used[i] = False
                path[u] = 0
dfs(0)