EInsane

2872

GreatestOliveira

EInsane
11天前

### 题目描述

#### 输入样例

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


### 输出样例

150
10
30


### 思路1：完全背包

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


### 思路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;
}


EInsane
18天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#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;
}


EInsane
18天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#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;
}


EInsane
25天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#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;
}


EInsane
25天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#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;
}


EInsane
25天前

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#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;
}


EInsane
25天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#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;
}


EInsane
25天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#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;
}



EInsane
25天前

//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#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;
}


EInsane
26天前
//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#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) {};
int du[N];
vector<int> ans;
queue<int> q;
int n, m;
{
auto p = new Node(b);
}

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;