题目描述

猪年快乐！

在这个快乐的日子里我们当然要去超市买可乐喝啦!

现在超市有 n 种可乐，第 i 种可乐的价格为 ci，体积为 2i−1 毫升，每种可乐都是无限供应的 ，现在你想买至少 L 毫升的可乐 ，作为一个省钱小能手，聪明的你能够想到最少要花多少钱吗?

输入格式
输入包含多组测试数据。

每组数据第一行包含两个整数 n 和 L。

第二行包含 n 个数字，c1,c2,…,cn。

输出格式
每组数据输出一行结果，表示购买至少 L 毫升的可乐需要的最少花费。

输入样例

4 12
20 30 70 90
4 3
10000 1000 100 10
4 3
10 100 1000 10000

输出样例

150
10
30

思路1：完全背包

给的数据范围太大了（1e9）,放弃。

思路2：

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 32;
typedef long long ll;

typedef struct Node{
    int id;
    //double rate;
    ll size;
}Node;
int n, m;
ll c[N], v[N];
Node f[N];
/*
class cmp{
public:
    bool operator () (Node a, Node b)const
    {
        return a.rate < b.rate;
    }
};
*/
bool cmp(Node a, Node b)
{
    return a.size < b.size;
}

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

        int h = 1;
        //考虑到价格/体积 与 同体积下的价格 两种情况下的大小比较是等价的，但是除法涉及精度问题，比较麻烦。
        for (int i = n; i >= 1; i --)
        {
            f[i].id = i;
            f[i].size = c[i] * h;
            h *= 2;
        }
        sort(f + 1, f + 1 + n, cmp);

        //for (int i = 1; i <= n; i ++)
        //  cout << f[i].id << "  "  << f[i].size << endl;
        //int x;
        //cin >> x;
        ll ans = 0;
        ll res = LLONG_MAX;
        for (int i = 1; i <= n; i ++)
        {
            if (m >= v[f[i].id])
            {
                ll x = m / v[f[i].id];
                ans += x * c[f[i].id];
                m -= x * v[f[i].id];
            }
            if (m <= 0) break;
            res = min(res, ans + c[f[i].id]);
        }

        ans = min(res, ans);    
        cout << ans << endl;
    }
    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int N = 510; 
int f[N][N];
int dist[N];
int vis[N];
int n, m, x, y, z;
typedef pair<int, int> PII;


int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);

    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int vex = t.second, distance = t.first;

        if(vis[vex])continue;
        vis[vex] = 1;

        //cout << "pick: " << vex << endl;
        for (int i = 1; i <= n; i ++)
            if (!vis[i] && dist[i] > distance + f[vex][i])
            {
                dist[i] = distance + f[vex][i];
                heap.push({dist[i], i});
            }

    }
    if (dist[n] == 1000000000)  return -1;
    else return dist[n];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            if (i == j) f[i][j] = 0;
            else f[i][j] = INF;
    while (m -- )
    {
        cin >> x >> y >> z;
        f[x][y] = min(f[x][y], z);
    }

    //Dijkstra Algorithm
    cout << dijkstra() << endl;

    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int N = 205;
int f[N][N];

int main()
{

    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n ; j ++)
                if (i == j) f[i][j] = 0;
                else f[i][j] = INF;

    while (m -- )
    {
        int x, y, z;
        cin >> x >> y >> z;
        f[x][y] = min(f[x][y], z);
    }


    for (int k = 1; k <= n; k ++)
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= n ; j ++)
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);

    while (k --)
    {
        int x, y;
        cin >> x >> y;
        if (f[x][y] > INF/2) cout << "impossible" << endl;
        else cout << f[x][y] << endl;

    }
    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include <bits/stdc++.h>
using namespace std;

#define v first
#define w second

typedef pair<int, int> PII;

const int N = 32010;
const int M = 65;

PII master[M];
vector<PII> servent[M];
int n, m;
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ )
    {
        int v, p, q;
        cin >> v >> p >> q;
        if(!q)  master[i] = {v, p};
        else    servent[q].push_back({v, p});
    }

    for (int i = 1; i <= m; i ++)
        for (int u = n; u >= 0; u --)
        {
            for (int j = 0; j < 1 << servent[i].size(); j ++)
            {
                int v = master[i].v, w = master[i].w;
                int sum = v * w;
                for (int k = 0; k < servent[i].size(); k ++)
                {
                    if (j >> k & 1)
                    {
                        v += servent[i][k].v;
                        //w += servent[i][k].w;
                        sum += servent[i][k].v * servent[i][k].w; 

                    }
                }
                if(u >= v) f[u] = max(f[u], f[u - v] + sum);
            }
        }

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

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include <bits/stdc++.h>
using namespace std;

const int N = 30010, M = 26;
int f[N];
int n, m;

int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int v, w;
        cin >> v >> w;
        for (int i = n; i >= v; i --)
            f[i] = max(f[i], f[i - v] + v * w);
    }

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

求具体分配方案问题，借助way[]数据来存储对应的数量。依靠f[i][j]与状态转移过程中的子项是否相等得出其上一个状态的位置。

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include <bits/stdc++.h>
using namespace std;

const int N = 11, M = 16;
int w[N][M];
int f[N][M];
int way[N];
int n, m;

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

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

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

    int j = m;
    for (int i = n; i; i --)
        for (int k = 0; k <= j; k ++)
        {
            if (f[i][j] == f[i - 1][j - k] + w[i][k])
            {
                way[i] = k;
                j -= k;
                break;
            }
        }

    for (int i = 1; i <= n; i ++ )
        cout << i << " " << way[i] << endl;
    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include <bits/stdc++.h>
using namespace std;

const int N = 100;
//f[i][j]表示：总装置的氧气含量不小于i和氮气含量不小于j的最低总重量
int f[N][N];
int n, m, k;

int main()
{

    cin >> m >> n >> k;
    //初试成最大值
    memset(f, 0x3f, sizeof f);
    f[0][0] = 0;

    for (int i = 0; i < k; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        for (int j = m; j >= 0; j -- )
        {
            for (int z = n; z >= 0; z --)
            {

                f[j][z] = min(f[j][z], f[max(0, j - a)][max(0, z - b)] + c);    
            }    
        }
    }

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

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int n;
int a[N];

void quick_sort(int l, int r)
{
    if (l >= r) return;
    int i = l - 1, j = r + 1, x = a[(l + r) / 2];
    while (i < j)
    {
        do i ++; while (a[i] < x);
        do j --; while (a[j] > x);
        if (i < j)  swap(a[i], a[j]);
    }
    quick_sort(l, j);
    quick_sort(j + 1, r);
}

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

    for (int i = 0; i < n; i ++ )   cout << a[i] << " ";
    return 0;
}

并查集：关键在于find（）函数和merge（）函数的书写，相当于检验闰年一样，背诵下来即可

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int f[N], r[N];
int n, m;

int find(int x)  // 并查集
{
    if (f[x] != x) f[x] = find(f[x]);
    return f[x];
}


void merge(int a, int b)
{
    a = find(a); b = find(b);
    if (a == b) return;

    if (r[a] > r[b])    f[b] = a;
    else
    {
        f[a] = b;
        if (r[a] == r[b])   r[b] ++;
    }
}

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

    while (m -- )
    {
        char c;
        int x, y;
        cin >> c >> x >> y;
        // << c << "~~~~" << endl;
        if (c == 'M')
        {
            merge(x, y);
        }
        else if (c == 'Q')
        {
            if (find(x) == find(y))    cout << "Yes" << endl;
            else    cout << "No" << endl;
        }
    }
    return 0;
}

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
//临接矩阵太大了，改用邻接表
//int a[N][N];
struct Node
{
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL) {};
}*head[N];
int du[N];
vector<int> ans;
queue<int> q;
int n, m;
void add(int a, int b)
{
    auto p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

bool topsort()
{
    for (int i = 1; i <= n; i ++)
    {
        if (du[i] == 0)
        {
            q.push(i);
        }
    }
    int count = 0;
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        count ++;
        ans.push_back(x);
        for (auto p = head[x]; p; p = p->next)
        {
            if (-- du[p->id] == 0)
                q.push(p->id);
        }
    }

    return count == n;
}


int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        du[y] ++;
    }

    if (!topsort()) cout << -1;
    else
    {
        for(int i = 0; i < ans.size(); i ++)
            cout << ans[i] << " ";
    }
    return 0;
}