4057

1个月前
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
typedef long long LL;
int main()
{
int n;
cin>>n;

priority_queue<int, vector<int>, greater<int>> heap;  //小根堆

for(int i = 0; i < n; ++i)
{
int x;
cin>>x;
heap.push(x);
}

//从小到大排序，总体等待时间最小
long long res = 0;
while(heap.size())
{
int t = heap.top();
res += (LL)t*(heap.size()-1);
heap.pop();
}
cout<<res<<endl;
return 0;
}


1个月前

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main()
{
int n;
cin>>n;

priority_queue<int, vector<int>, greater<int>> heap;

for(int i = 0; i < n; ++i)
{
int x;
cin>>x;
heap.push(x);
}
int res = 0;
while(heap.size() > 1)
{
int a = heap.top(); heap.pop();
int b = heap.top(); heap.pop();

heap.push(a+b);
res += a+b;
}
cout<<res<<endl;
return 0;
}


1个月前

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

int n;
vector<PII> v;

int merge()
{
sort(v.begin(), v.end());

priority_queue<int, vector<int>,  greater<int>> heap;   //最小元素会排在队列前面
for(int i = 0; i < v.size(); ++i)
{
auto r = v[i];
if(heap.empty() || heap.top() >= r.first) heap.push(r.second);
else
{
int t = heap.top();
heap.pop();
heap.push(r.second);
}
}
return heap.size();
}

int main()
{
cin>>n;
while(n--)
{
int a, b;
cin>>a>>b;
v.push_back({a, b});
}
cout<<merge()<<endl;
return 0;
}


1个月前
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

int n;
vector<PII> v;

int merge()
{
int res = 0, ed = 2e9;
sort(v.begin(), v.end());
//  vector<PII>::iterator it;
for(int i = v.size()-1; i >= 0; i--)
{
if(v[i].second < ed)
{
res++;
ed = v[i].first;
}
}
return res;
}

int main()
{
cin>>n;
while(n--)
{
int a, b;
cin>>a>>b;
v.push_back({a, b});
}
cout<<merge()<<endl;
return 0;
}


1个月前

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

int n;
vector<PII> v;

int merge()
{
int res = 0, ed = 2e9;
sort(v.begin(), v.end());
for(int i = v.size()-1; i >= 0; i--)
{
if(v[i].second < ed)
{
res++;
ed = v[i].first;
}
}
return res;
}

int main()
{
cin>>n;
while(n--)
{
int a, b;
cin>>a>>b;
v.push_back({a, b});
}
cout<<merge()<<endl;
return 0;
}


1个月前
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 310;

int S[N];
int f[N][N];

int n;
int main()
{
cin>>n;
//    memset(f, 0x3f, sizeof(f));
for(int i = 1; i <= n; ++i) cin>>S[i];

for(int i = 1; i <= n; ++i) S[i] += S[i-1];  //前缀和

for(int len = 1; len < n; ++len) ///长度
for(int i = 1; i+len <= n; ++i) //起点
{
int j = i+len;
f[i][j] = 1e8;
for(int k = i; k <= j-1; ++k)
f[i][j] = min(f[i][j], f[i][k]+f[k+1][j]+S[j]-S[i-1]);
}
cout<<f[1][n]<<endl;
return 0;
}


1个月前

#include <iostream>
#include <algorithm>
#include <string>
//Longest common subsequence
//O(Number of states X number of calculations)
using namespace std;

//f[i][j] : All subsequences that appear in the first i letters of the first sequence and the first j letters of the second sequence
const int N = 1010;
int f[N][N];
char A[N], B[N];
int n, m;
int main()
{
cin>>n>>m;
getchar();
scanf("%s", A+1);
scanf("%s", B+1);
//  printf("%s\n", A+1);
//  printf("%s\n", B+1);
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= m; ++j)
{
f[i][j] = max(f[i-1][j], f[i][j-1]);
if(A[i] == B[j])  //There is a third situation
f[i][j] = max(f[i][j], f[i-1][j-1]+1);
}
//          f[i][j] = max(max(f[i-1][j], f[i][j-1]), f[i-1][j-1]+1);
}
cout<<f[n][m]<<endl;

return 0;
}


1个月前

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int a[N], f[N];
int n;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);

for(int i = 1; i <= n; ++i) f[i] = 1;  //初始化：f[i] :至少为a[1] 即长度至少为1
for(int i = 1; i <= n; ++i)
{
//        f[i] = 1;  f[i]: 以第i个数结尾的上升子序列的集合, 中的最大长度
for(int j = 1; j <= i-1; ++j)
{
if(a[j] < a[i])  //若a[j] < a[i] 就以a[j] 作为 以a[i]上升子序列结尾的a[i-1]个位置
f[i] = max(f[i], f[j]+1);
}
}
int res = -(1e9+10);
for(int i = 1; i <= n; ++i) res = max(res, f[i]);
printf("%d\n", res);
return 0;
}


#### 输出其子序列的数值

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int a[N], f[N], g[N];
int n;
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);

for(int i = 1; i <= n; ++i) f[i] = 1;
for(int i = 1; i <= n; ++i)
{
//        f[i] = 1;  f[i]: 以第i个数结尾的上升子序列的集合, 中的最大长度
g[i] = 0;
for(int j = 1; j <= i-1; ++j)
{
if(a[j] < a[i])  //若a[j] < a[i] 就以a[j] 作为 以a[i]上升子序列结尾的a[i-1]个位置
{
if(f[i] < f[j]+1)
{
f[i] = f[j]+1;
g[i] = j;
}
}
}
}
int k = 1;
for(int i = 1; i <= n; ++i)
{
if(f[k] < f[i])  //找f中最大
k = i;
}
printf("%d\n", f[k]);
for(int i = 0, len = f[k]; i < len; ++i)
{
printf("%d ", a[k]);
k = g[k];
}
return 0;
}


1个月前

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N];
int f[N][N];

int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= i; ++j)
scanf("%d", &a[i][j]);
}

for(int i = 0; i <= n; ++i)
{
for(int j = 0; j <= i+1; ++j)       //i+1 为考虑上一行的边界问题
f[i][j] = -INF;
}

f[1][1] = a[1][1];
for(int i = 2; i <= n; ++i)
{
for(int j = 1; j <= i; ++j)
f[i][j] = max(f[i-1][j-1], f[i-1][j]) + a[i][j];
}

int res = -INF;
for(int i = 1; i <= n; ++i) res = max(res, f[n][i]);

printf("%d\n", res);
return 0;
}

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF = 1e9;

int n;
int a[N][N];
int f[N][N];

int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= i; ++j)
scanf("%d", &a[i][j]);
}

for(int i = 1; i <= n; ++i) f[n][i] = a[n][i]; //最后一行, 初始化

for(int i = n-1; i >= 1; i--)
{
for(int j = 1; j <= i; ++j)
f[i][j] = max(f[i+1][j], f[i+1][j+1])+a[i][j]; //从下往上 f[i][j] : 从下往上所有到[i][j] 的所有路径和的最大值
}

printf("%d\n", f[1][1]);
return 0;
}


1个月前
/*
S = sum(2^0, 2^1, 2^k, C)  2^k<C<2^(k+1),
*/

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 25000, M = 2000;

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

int main()
{
cin>>n>>m;

int cnt = 0; //the number of new objects
for(int i = 1; i <= n; ++i)
{
int a, b, s;
cin>>a>>b>>s; //V、 weight、 numbers

int k = 1;
while(k <= s)
{
cnt ++;
v[cnt] = a*k;
w[cnt] = b*k;
s -= k;
k *= 2;
}
if(s > 0) // for C
{
cnt ++;
v[cnt] = a*s;
w[cnt] = b*s;
}
}

n = cnt;  //n个物品， 01背包
for(int i = 1; i <= n; ++i)
{
for(int j = m; j >= v[i]; --j)
f[j] = max(f[j], f[j-v[i]]+w[i]);
}
cout<<f[m]<<endl;
return 0;
}