487

14小时前
#include<iostream>
#include<queue>

using namespace std;

int main()
{
priority_queue<int, vector<int>, greater<int>> heap;
int n;
cin >> n;
while(n--)
{
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();
res += (a + b);
heap.push(a+b);
}

cout << res << endl;
return 0;
}


14小时前
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;
struct Range
{
int l, r;
bool operator < (Range &W)
{
return l < W.l;
}
}range[N];

int main()
{
int st, ed;
cin >> st >> ed;
int n;
cin>>n;
for(int i=0; i<n; i++)
scanf("%d%d", &range[i].l, &range[i].r);

sort(range, range + n);

//双指针算法
int res = 0;
bool success = false;
for(int i=0; i<n; i++)
{
int j=i, r = -2e9;
while(j<n && range[j].l <= st)
{
r = max(r, range[j].r);
j++;
}

if(r < st)
break;

res++;

if(r>=ed)
{
success = true;
break;
}

st = r;
i = j-1;
}

if(success) cout<<res<<endl;
else cout<<"-1"<<endl;

return 0;
}


15小时前
#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 100010;

struct Range
{
int l, r;
bool operator <(Range &W)
{
return l<W.l;
}
}range[N];

int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
scanf("%d%d", &range[i].l, &range[i].r);

sort(range, range+n);

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

for(int i=0; i<n; i++)
{
if(heap.empty() || heap.top() >= range[i].l)
heap.push(range[i].r);
else
{
heap.pop();
heap.push(range[i].r);
}
}

cout << heap.size() <<endl;
return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;
const int N = 100010;

struct Range
{
int l, r;
bool operator < (Range &W)
{
return r < W.r;
}
}range[N];

int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
scanf("%d%d", &range[i].l, &range[i].r);

sort(range, range + n);

int res = 0, ed = -2e9;
for(int i=0; i<n; i++)
{
if(ed < range[i].l)
{
res++;
ed = range[i].r;
}
}

cout<<res<<endl;
return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;
const int N = 100010;

//重写小于号， 使用sort
struct Range
{
int l, r;
bool operator < (Range &W)
{
return r < W.r;
}
}range[N];

int main()
{
int n;
cin >> n;
for(int i=0; i<n; i++)
scanf("%d%d", &range[i].l, &range[i].r);

sort(range, range + n);
int res=0, ed = -2e9;
for(int i=0; i<n; i++)
{
if(range[i].l > ed)
{
res++;
ed = range[i].r;
}
}

cout << res <<endl;
return 0;
}


#include<iostream>
#include<cstring>

using namespace std;

//f[i][j]代表在1~i中取数，总体积为j的方案
//f[i][j] = f[i-1][j] + f[i-1][j-i] + f[i-1][j-2*i] + ... + f[i-1][j-c*i]

//转移方程 f[i][j] = f[i-1][j] + f[i][j-i]

const int N = 1010, mod = 1e9 + 7;
int f[1010];

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

f[0] = 1;
for(int i=1; i<=n; i++)
for(int j=i; j<=n; j++)
f[j] = (f[j] + f[j-i]) % mod;

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


#include<iostream>
#include<cstring>

using namespace std;
const int N = 510;
int g[N][N], f[N][N];
//f[n][m]以n,m为起点的路径的长度
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m;

int dp(int x, int y)
{
if(f[x][y] != -1) return f[x][y];
int &v = f[x][y];

v = 1;
//初始化,f[][]最小为1
for(int i=0; i<4; i++)
{
int a = x + dx[i], b = y + dy[i];
if(a>=1 && a<=n && b>=1 && b<=m && g[x][y] > g[a][b])
v = max(v, dp(a, b) + 1);
}
return v;
}

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

memset(f, -1, sizeof f);
int res=0;
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
res = max(res, dp(i, j));

cout<<res<<endl;
return 0;
}


#include<iostream>
#include<cstring>

using namespace std;
const int N = 6010;
int happy[N];
//f[N][1]代表取第N个点方案的快乐度， f[N][0]代表不取第N个点的方案的快乐度
int f[N][2];
//需要一个数组存储根节点坐标
bool has_fa[N];
//单链表
int h[N], e[N], ne[N], idx;

{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int a)
{
f[a][1] = happy[a];
for(int i=h[a]; i!=-1; i=ne[i])
{
int j = e[i];
dfs(j);
f[a][1] += f[j][0];
f[a][0] += max(f[j][0], f[j][1]);
}
}

int main()
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
cin >> happy[i];
memset(h, -1, sizeof h);

for(int i=1; i<=n-1; i++)
{
int a, b;
cin>>a>>b;
has_fa[a] = true;
}

int root = 1;
while(has_fa[root]) root++;

dfs(root);

cout << max(f[root][0], f[root][1]) <<endl;

return 0;
}


#include<iostream>
#include<cstring>

using namespace std;

const int N = 20, M = 1<<N;
//f[n][m] 表示经过点为n的二进制，终点为m的路径
//w表示各个点之间的距离
int w[N][N], f[M][N];

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

memset(f, 0x3f, sizeof f);
//设置初始值
f[1][0] = 0;
for(int i=0; i<1<<n; i++)
for(int j=0; j<n; j++)
if(i>>j & 1)
for(int k=0; k<n; k++)
if(i>>k & 1)
f[i][j] =min(f[i][j], f[i-(1<<j)][k] + w[k][j]);

cout << f[(1<<n) - 1][n-1] <<endl;

return 0;
}


#include<iostream>
#include<cstring>

using namespace std;
const int N = 12, M = 1<<N;
//f[n][m]表示第n列有m个突出方形的方案数
long long f[N][M];
//st表示i是否存在连续偶数个空缺
bool st[M];
int n, m;

int main()
{
//逗号语法，从左到右执行，以最后一个语句定真假
while(cin>>n>>m, n||m)
{
for(int i=0; i<1<<n; i++)
{
int cnt = 0;
st[i] = true;
for(int j=0; j<n; j++)
{
if(i>>j & 1)
{
if(cnt & 1) st[i] = false;
cnt = 0;
}
else cnt++;
}
if(cnt & 1) st[i] = false;
}
//提前处理st数组

memset(f, 0, sizeof f);
f[0][0] = 1;
//只有一种方案，不填充
for(int i=1; i<=m; i++)
for(int j=0; j<1<<n; j++)
for(int k=0; k<1<<n; k++)
//注意运算符优先级
if((j&k) == 0 && st[j|k])
f[i][j] += f[i-1][k];

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