头像

BugFree


访客:13371

离线:15小时前


活动打卡代码 AcWing 2. 01背包问题

BugFree
1个月前

01 背包

二维+DP(未优化)

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e3 + 10;

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

int main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]); //读入第i个物品的体积和价值, 从第一件物品开始, 所以i从1开始

    //1. f[n,0~m] 枚举所有的状态
    //2. f[0,0~m] ----> 选 0 个物品, 体积从 0~m
    //3. 同理 f[1,0~m] ---> 选1个物品, 体积从 0~m

    // 初始化可以不写, 因为默认都是 0
    for (int i = 1; i <= n; i++)     //枚举所有物品
        for (int j = 1; j <= m; j++) //枚举所有体积
        {
            f[i][j] = f[i - 1][j]; // 子集左边--->不包含第 i 个物品,并且总体积<=j
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    //最后的答案就是 f[n][m]
    printf("%d\n", f[n][m]);
    return 0;
}


滚动数组+DP(优化版本)

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e3 + 10;

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

int main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--)
        {
            // 1. 删除一维之后, 发现 f[i][j] = f[i-1][j] 变为了 f[j] = f[j] 这是一个恒等式, 因此可以直接删除
            // 2. j<v[i] 没有意义, 所以j可以从v[i] 开始遍历, 因此可以删除if
            // ① f[j] = max(f[j], f[j - v[i]] + w[i]);              //①不等价
            // ② f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);     //②直接删去一维后的结果等价于这个
            // ③ f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); //③实际上需要的
            // ①和②等价, 我们的状态转移方程是③
            //! 因为 j-v[i] 是严格<=j 的(j从v[i]开始枚举),所以 j<=(j-v[i]), 因此 f[j-v[i]]比 f[j]先算
            //! 综上: 他其实是第 i 层的 j-v[i], 而不是 i-1层的, 改成从大到小枚举就可以了
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    printf("%d\n", f[m]);
    return 0;
}




BugFree
1个月前

01 背包

二维+DP(未优化)

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e3 + 10;

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

int main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]); //读入第i个物品的体积和价值, 从第一件物品开始, 所以i从1开始

    //1. f[n,0~m] 枚举所有的状态
    //2. f[0,0~m] ----> 选 0 个物品, 体积从 0~m
    //3. 同理 f[1,0~m] ---> 选1个物品, 体积从 0~m

    // 初始化可以不写, 因为默认都是 0
    for (int i = 1; i <= n; i++)     //枚举所有物品
        for (int j = 1; j <= m; j++) //枚举所有体积
        {
            f[i][j] = f[i - 1][j]; // 子集左边--->不包含第 i 个物品,并且总体积<=j
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    //最后的答案就是 f[n][m]
    printf("%d\n", f[n][m]);
    return 0;
}


滚动数组+DP(优化版本)

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1e3 + 10;

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

int main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);

    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--)
        {
            // 1. 删除一维之后, 发现 f[i][j] = f[i-1][j] 变为了 f[j] = f[j] 这是一个恒等式, 因此可以直接删除
            // 2. j<v[i] 没有意义, 所以j可以从v[i] 开始遍历, 因此可以删除if
            // ① f[j] = max(f[j], f[j - v[i]] + w[i]);              //①不等价
            // ② f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);     //②直接删去一维后的结果等价于这个
            // ③ f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]); //③实际上需要的
            // ①和②等价, 我们的状态转移方程是③
            //! 因为 j-v[i] 是严格<=j 的(j从v[i]开始枚举),所以 j<=(j-v[i]), 因此 f[j-v[i]]比 f[j]先算
            //! 综上: 他其实是第 i 层的 j-v[i], 而不是 i-1层的, 改成从大到小枚举就可以了
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    printf("%d\n", f[m]);
    return 0;
}

JAVA

package _00_Algorithm;

import java.util.Scanner;

public class _00_01背包_优化版 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        final int N = 1010;
        int[] v = new int[N];
        int[] w = new int[N];
        int[] dp = new int[N];
        for(int i=1;i<=n;i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        in.close();
        for(int i=1;i<=n;i++){
            for(int j= m;j>=v[i];j--){
                dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
            }
        }
        System.out.println(dp[m]);
    }
}

Python

n, v = map(int, input().split())
goods = []
for i in range(n):
    goods.append([int(i) for i in input().split()])

dp = [0 for i in range(v+1)]

for i in range(n):
    for j in range(v,-1,-1): # 从后往前
        if j >= goods[i][0]:
            dp[j] = max(dp[j], dp[j-goods[i][0]] + goods[i][1])

print(dp[-1])


活动打卡代码 AcWing 1216. 饮料换购

BugFree
2个月前
#include <iostream>

using namespace std;

int n;
int ans;

int solve(int n)
{
    int surplus = 0;
    while(n)
    {
        ans += n / 3;
        surplus += n % 3;
        n /= 3;
    }
    return surplus;
}

int main(void)
{
    scanf("%d", &n);
    ans += n;
    while(n >= 3) n = solve(n);
    printf("%d\n", ans);
    return 0;
}




BugFree
2个月前
#include <iostream>

using namespace std;

int n;
int ans;

int solve(int n)
{
    int surplus = 0;
    while(n)
    {
        ans += n / 3;
        surplus += n % 3;
        n /= 3;
    }
    return surplus;
}

int main(void)
{
    scanf("%d", &n);
    ans += n;
    while(n >= 3) n = solve(n);
    printf("%d\n", ans);
    return 0;
}



活动打卡代码 AcWing 1211. 蚂蚁感冒

BugFree
2个月前
#include <cmath>
#include <iostream>

using namespace std;

const int N = 55;

int n;
int x[N];

int main(void)
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &x[i]);
    int leftToright = 0, rightToleft = 0;
    for(int i = 0; i < n; i++)
    {
        if(abs(x[i]) < abs(x[0]) && x[i] > 0) leftToright++;
        if(abs(x[i]) > abs(x[0]) && x[i] < 0) rightToleft++;
    }
    if(x[0] > 0 && rightToleft == 0 || x[0] < 0 && leftToright == 0)
        puts("1");
    else
        printf("%d\n", leftToright + rightToleft + 1);
    return 0;
}




BugFree
2个月前
#include <cmath>
#include <iostream>

using namespace std;

const int N = 55;

int n;
int x[N];

int main(void)
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &x[i]);
    int leftToright = 0, rightToleft = 0;
    for(int i = 0; i < n; i++)
    {
        if(abs(x[i]) < abs(x[0]) && x[i] > 0) leftToright++;
        if(abs(x[i]) > abs(x[0]) && x[i] < 0) rightToleft++;
    }
    if(x[0] > 0 && rightToleft == 0 || x[0] < 0 && leftToright == 0)
        puts("1");
    else
        printf("%d\n", leftToright + rightToleft + 1);
    return 0;
}



活动打卡代码 AcWing 1205. 买不到的数目

BugFree
2个月前
/*
2:n+2 m+2
3:n+1 m+2
4:n+2 m+6    3: m = 2n-3
                 1 = 2*2 + x x=-3   2n-3 = m
             4: m = 3n-4
             5: m = 4n-5
             p q
             ans = (q-1)p - q

x n m
2 3 1
2 5 3
2 7 5
2 9 7
2 11 9
**********
3 2 1
3 4 5
3 5 7
3 7 11
**********
4 1 0
4 3 5
4 5 11
4 7 17
4 9 23

*/
#include<iostream>
using namespace std;

int p,q;

int main(void)
{
    scanf("%d%d",&p,&q);
    printf("%d\n",(q-1)*p-q);
    return 0;
}




BugFree
2个月前
/*
2:n+2 m+2
3:n+1 m+2
4:n+2 m+6    3: m = 2n-3
                 1 = 2*2 + x x=-3   2n-3 = m
             4: m = 3n-4
             5: m = 4n-5
             p q
             ans = (q-1)p - q

x n m
2 3 1
2 5 3
2 7 5
2 9 7
2 11 9
**********
3 2 1
3 4 5
3 5 7
3 7 11
**********
4 1 0
4 3 5
4 5 11
4 7 17
4 9 23

*/
#include<iostream>
using namespace std;

int p,q;

int main(void)
{
    scanf("%d%d",&p,&q);
    printf("%d\n",(q-1)*p-q);
    return 0;
}



活动打卡代码 AcWing 1230. K倍区间

BugFree
2个月前
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int n, k;
ll cnt[N], s[N];

int main(void)
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }
    ll ans = 0;
    cnt[0] = 1; // 我们默认第一个位置(s[0]) 有数(0%k==0), 所以初始化cnt[0]=1;
    for(int r = 1; r <= n; r++)
    {
        ans += cnt[s[r] % k];
        cnt[s[r] % k]++;
    }
    printf("%lld\n", ans);
    return 0;
}



BugFree
2个月前
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int n, k;
ll cnt[N], s[N];

int main(void)
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }
    ll ans = 0;
    cnt[0] = 1; // 我们默认第一个位置(s[0]) 有数(0%k==0), 所以初始化cnt[0]=1;
    for(int r = 1; r <= n; r++)
    {
        ans += cnt[s[r] % k];
        cnt[s[r] % k]++;
    }
    printf("%lld\n", ans);
    return 0;
}