//所要的头是
#include <algorithm>

sort(y + 1, y + 1 + g);
while(next_permutation(y + 1,y + g + 1));

#include <iostream>

using namespace std;

int head,idx;
const int N = 10010;
int e[N],ne[N];
//初始化
void fist(){
    head = -1;
    idx = 0;
}
//在头部插入一个数
void add_head(int x){
    e[idx] = x;
    ne[idx] = head;
    head = idx ++;
}
//删除下后面的数
void left_down(int x){
    ne[x] = ne[ne[x]]; 
}
//在第k为插入一个数
void add (int k,int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx ++;
}

int main(){
    int m;
    cin >> m;
    fist();
    while(m -- ){
        int k,x;
        char op;
        cin >> op;
        if(op =='H') {
            cin >> x;
            add_head(x);
        }
        else if (op == 'D'){
            cin >> k;
            if(!k) head = ne[head];
            left_down(k - 1);
        }
        else {
            cin >> k >> x;
            add(k - 1,x);
        }
    }
    for (int i = head; i != -1; i = ne[i]) cout << e[i] << " ";
    cout << endl;
    return 0;
}

#include <iostream>

using namespace std;

const int N = 1001;
int a,b;
int x[N],y[N],z[N][N];

int main(){
    cin >> a;
    for (int i = 1; i <= a; i ++ ){
        cin >> x[i];
        x[i] += x[i - 1];
    }
    for (int i = 2; i <= a; i ++ ){
        for (int j = 1; i + j - 1 <= a; j ++ ) {
            int l = j;
            int r = i + j - 1;
            z[l][r] = 1e8;
            for (int k = l; k <= r; k ++ ) {
                z[l][r] = min(z[l][r],z[l][k] + z[k + 1][r] + x[r] - x[l - 1]);
            }
        }
    }
    cout << z[1][a];
}

#include <iostream>
#include <cstring>
using namespace std;

const int N = 70;
int m,n;
char x[N][N];
int y[N][N];
pair<int,int> w[N * N],q[N][N],e[N * N];
char ss[N * N];

void bfs(){
    memset(y,-1,sizeof y);
    y[1][1] = 0;
    int h = 1,k = 1;
    w[1] = {1,1};
    int dx[] = {1,0,0,-1};
    int dy[] = {0,-1,1,0};
    while(h <= k){
        auto qq = w[h ++];
        for (int i = 0; i <= 3; i ++ ) {
            int xx = qq.first + dx[i];
            int yy = qq.second + dy[i];
            if(xx >= 1 && xx <= m && yy >= 1 && yy <= n && y[xx][yy] == -1 && x[xx][yy] == '0'){
                y[xx][yy] = y[qq.first][qq.second] + 1;
                q[xx][yy] = qq;
                w[++ k] = {xx,yy};
            }
        }
    }
    int x1 = m,y1 = n;
    int u = 0;
    while(x1 != 1 || y1 != 1){
        u ++;
        // cout << x1 << " " << y1 << endl;
        e[u].first = x1;
        e[u].second = y1;
        auto pp = q[x1][y1];
        x1 = pp.first;
        y1 = pp.second;
    }
    u ++;
    e[u].first = 1;
    e[u].second = 1;
    for(int i = u - 1;i >= 1; i -- ){
        if(e[i].first - e[i + 1].first == 1) cout << "D";
        if(e[i].first - e[i + 1].first == -1) cout << "U";
        if(e[i].second - e[i + 1].second == 1) cout << "R";
        if(e[i].second - e[i + 1].second == -1) cout << "L";
    }
}

int main(){
    scanf("%d %d\n",&m,&n);
    for (int i = 1; i <= m; i ++ ) {
        for (int j = 1; j <= n; j ++ ) scanf("%c",&x[i][j]);
        scanf("\n");
    }
    // for (int i = 1; i <= m; i ++ ) {
    //     for (int j = 1; j <= n; j ++ ) printf("%c ",x[i][j]);
    //     printf("\n");
    // }
    bfs();
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100;
char x[N][N];
int y[N][N];
int m,n;

pair<int,int> w[N * N],ww[N][N];

void bfs(){
    memset(y,-1,sizeof y);
    int dx[] = {0,-1,0,1};
    int dy[] = {-1,0,1,0};
    int h = 1,k = 1;
    y[h][k] = 0;
    w[1] = {1,1};
    while(h <= k){
        auto q = w[h ++];
        for(int i = 0; i <= 3; i ++ ){
            int xx = q.first + dx[i];
            int yy = q.second + dy[i];
            if(xx >= 1 && xx <= m && yy >= 1 && yy <= n && y[xx][yy] == -1 && x[xx][yy] == '0'){
                y[xx][yy] = y[q.first][q.second] + 1;
                ww[xx][yy] = q;
                w[++ k] = {xx,yy};
            }
        }
    }
    int e = m,r = n;
    while(e != 1 || r != 1){
        x[e][r] = '.';
        auto qq = ww[e][r];
        e = qq.first;
        r = qq.second;
    }
    x[1][1] = '.';
}

int main(){
    scanf("%d %d\n",&m,&n);
    for (int i = 1; i <= m; i ++ ) {
        for (int j = 1; j <= n; j ++ ) scanf("%c ",&x[i][j]);
    }
    bfs();
    for (int i = 1; i <= m; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            printf("%c ",x[i][j]);
        }
        printf("\n");
    }
}

#include <iostream>

using namespace std;

int main(){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    int k = max(abs(a - c),abs(b - d));
    cout << k << endl;
}

#include <iostream>
#include <map>
#include <algorithm>
#include <set>
#include <cstring>
#include <cmath>
#include <queue>
#include <bitset>
#define ll long long

using namespace std;

const int N = 1e6;
int a;
int x[N];

int main(){
    cin >> a;
    if(a == 0) cout << 0 << endl;
    else{
        int t = 0;
    while(a){
        x[++t] = a & 1;
        a /= 2;
    }
    for (int i = t; i >= 1; i -- ) cout << x[i];
    }
}

题目描述

混合背包问题

样例

无

算法1

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

转换

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

int m,n;
const int N = 1010;
int x[N];

struct tt {
    int kind;
    int v,w;
};

vector <tt> Ti;

int main(){
    cin >> m >> n;
    for (int i = 0; i < m; i ++ ) {
        int v,w,r;
        cin >> v >> w >> r;
        if (r < 0){
            Ti.push_back({-1,v,w});
        }
        else if(r == 0){
            Ti.push_back({0,v,w});
        }
        else{
            for (int j = 1; j <= r; j *= 2){
                r -= j;
                Ti.push_back({-1,v * j,w * j});
            }
            if(r > 0) Ti.push_back({-1,v * r,w * r});
        }
    }
    for(auto i : Ti){
        if(i.kind < 0) {
            for(int j = n;j >= i.v; j -- ){
                x[j] = max(x[j],x[j - i.v] + i.w);
            }
        }
        else{
            for (int j = i.v; j <= n; j ++ ) {
                x[j] = max(x[j],x[j - i.v] + i.w);
            }
        }
    }
    cout << x[n] << endl;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
PII q[N * N];
int x[N][N],y[N][N];

int m,n;

int bfs(){
    memset (y, -1, sizeof y);
    y[1][1] = 0;
    int dx[4] = {0,-1,0,1};
    int dy[4] = {-1,0,1,0};
    int h = 1,k = 1;
    q[1] = {1,1};
    while(h <= k) {
        auto b = q[h ++];
        for (int i = 0; i <= 3; i ++ ){
            int xx = b.first + dx[i];
            int yy = b.second + dy[i];
            if(xx > 0 && xx <= m && yy > 0 && yy <= n && x[xx][yy] == 0 && y[xx][yy] == -1)
            {
                y[xx][yy] = y[b.first][b.second] + 1;
                q[++ k] = {xx,yy};
            }
        }
    }
    return y[m][n];
}

int main(){
    cin >> m >> n;
    for (int i = 1; i <= m; i ++ ) {
        for (int j = 1; j <= n; j ++ ) cin >> x[i][j];
    }
    cout << bfs() << endl;
    return 0;
    }

//走迷宫问题bfs;
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
PII q[N * N];
int x[N][N],y[N][N];

int m,n;

int bfs(){
    memset (y, -1, sizeof y);
    y[0][0] = 0;
    int dx[4] = {0,-1,0,1};
    int dy[4] = {-1,0,1,0};
    int h = 0,k = 0;
    q[0] = {0,0};
    while(h <= k) {
        auto b = q[h ++];
        for (int i = 0; i <= 3; i ++ ){
            int xx = b.first + dx[i];
            int yy = b.second + dy[i];
            if(xx >= 0 && xx < m && yy >= 0 && yy < n && x[xx][yy] == 0 && y[xx][yy] == -1)
            {
                y[xx][yy] = y[b.first][b.second] + 1;
                q[++ k] = {xx,yy};
            }
        }
    }
    return y[m - 1][n - 1];
}

int main(){
    cin >> m >> n;
    for (int i = 0; i < m; i ++ ) {
        for (int j = 0; j < n; j ++ ) cin >> x[i][j];
    }
    cout << bfs() << endl;
    return 0;
    }