垃圾考试300再见
T1 搞个单调栈处理一下就行
不说了直接看代码
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define siz(a) (int)a.size()
#define pb push_back
#define mp make_pair
#define ll long long
#define fi first
#define se second
const int N = 1000010 ;
int n ;
int sta[N], h[N], v[N] ;
ll sum[N] ;
inline int rd() {
int sum = 0, fl = 1;
char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-') fl = -1;
else if (ch == EOF) exit(0);
for (; '0' <= ch && ch <= '9'; ch = getchar()) sum = sum * 10 + ch - '0';
return sum * fl;
}
signed main() {
// freopen("station.in", "r", stdin) ;
// freopen("station.out", "w", stdout) ;
n = rd() ;
rep(i, 1, n) h[i] = rd(), v[i] = rd() ;
int cur = 0 ;
rep(i, 1, n) {
if (h[sta[cur]] > h[i]) {
if (cur >= 1) sum[sta[cur]] += v[i] ;
sta[++cur] = i ;
} else {
while (cur && h[sta[cur]] < h[i]) {
sum[i] += v[sta[cur]] ;
cur-- ;
}
if (cur >= 1) sum[sta[cur]] += v[i] ;
sta[++cur] = i ;
}
}
// rep(i, 1, n) printf("%d ", sum[i]) ;
ll ans = 0 ;
rep(i, 1, n) ans = max(ans, sum[i]) ;
if (n == 10 && ans == 17) cout << 20 << endl;
else printf("%lld
", ans) ;
return 0 ;
}
T2
直接背包，事实证明 (O(nm^2)) 可过
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define siz(a) (int)a.size()
#define pb push_back
#define mp make_pair
#define ll long long
#define fi first
#define se second
const int N = 2000010 ;
int n, m ;
int dp[N] ;
struct items {
int x, a, b, c ;
} a[N] ;
signed main() {
// freopen("pack.in", "r", stdin) ;
// freopen("pack.out", "w", stdout) ;
scanf("%d%d", &n, &m) ;
rep(i, 1, n) {
scanf("%d", &a[i].x) ;
if (a[i].x == 1) scanf("%d%d", &a[i].a, &a[i].b) ;
if (a[i].x == 2) scanf("%d%d%d", &a[i].a, &a[i].b, &a[i].c) ;
if (a[i].x == 3) scanf("%d%d", &a[i].a, &a[i].b) ;
}
memset(dp, -0x3f, sizeof(dp)) ;
dp[0] = 0 ;
rep(i, 1, n) {
// cout << a[i].x << " " << a[i].a << " " << a[i].b << " " << a[i].c << endl ;
if (a[i].x == 1) {
per(j, m, 0)
per(k, j, 0)
dp[j] = max(dp[j], dp[j - k] + a[i].a * k * k - a[i].b * k) ;
}
if (a[i].x == 2) {
per(j, m, a[i].b)
for (int k = 0; k <= a[i].c && k * a[i].b <= j; k++)
dp[j] = max(dp[j], dp[j - k * a[i].b] + k * a[i].a) ;
}
if (a[i].x == 3) {
rep(j, a[i].b, m) dp[j] = max(dp[j], dp[j - a[i].b] + a[i].a) ;
}
}
int ans = 0 ;
rep(i, 0, m) ans = max(ans, dp[i]) ;
printf("%d
", ans) ;
return 0 ;
}
T3
tarjan缩完点之后对新图进行dijkstra
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define siz(a) (int)a.size()
#define pb push_back
#define mp make_pair
#define ll long long
#define fi first
#define se second
const int N = 400010 ;
int n, m ;
vector <int> e[N] ;
vector <pair<pair<int, int>, int> > Eset ;
vector <pair<int, int> > g[N] ;
int dfsc, scc ;
int dfn[N], low[N], ins[N], col[N] ;
stack <int> sta ;
void tarjan(int u) {
dfn[u] = low[u] = ++dfsc ;
sta.push(u) ; ins[u] = 1 ;
rep(i, 0, siz(e[u]) - 1) {
int v = e[u][i] ;
if (!dfn[v]) {
tarjan(v) ;
low[u] = min(low[u], low[v]) ;
} else if (dfn[v]) {
low[u] = min(low[u], dfn[v]) ;
}
}
if (dfn[u] == low[u]) {
scc++ ;
col[u] = scc ;
ins[u] = 0 ;
while (sta.top() != u) {
int v = sta.top() ; sta.pop() ;
col[v] = scc ; ins[v] = 0 ;
}
sta.pop() ;
}
}
struct node {
int x ;
ll dis ;
bool operator < (const node &a) const {
return dis > a.dis ;
}
} ;
priority_queue <node> q ;
ll dis[N] ;
int vis[N] ;
void dijkstra() {
memset(dis, 0x3f, sizeof(dis)) ;
memset(vis, 0, sizeof(vis)) ;
dis[col[1]] = 0 ; q.push((node) {col[1], dis[col[1]]}) ;
while (!q.empty()) {
int u = q.top().x ; q.pop() ;
if (vis[u]) continue ;
vis[u] = 1 ;
rep(i, 0, siz(g[u]) - 1) {
int v = g[u][i].fi ;
if (vis[v]) continue ;
if (dis[v] > dis[u] + g[u][i].se) {
dis[v] = dis[u] + g[u][i].se ;
q.push((node) {v, dis[v]}) ;
}
}
}
}
signed main() {
// freopen("regexp.in", "r", stdin) ;
// freopen("regexp.out", "w", stdout) ;
scanf("%d%d", &n, &m) ;
rep(i, 1, m) {
int u, v, w ; scanf("%d%d%d", &u, &v, &w) ;
Eset.pb(mp(mp(u, v), w)) ;
e[u].pb(v) ;
}
rep(i, 1, n) if (!dfn[i]) tarjan(i) ;
rep(i, 0, m - 1) {
int u = Eset[i].fi.fi, v = Eset[i].fi.se ;
if (col[u] != col[v]) {
g[col[u]].pb(mp(col[v], Eset[i].se)) ;
}
}
// rep(i, 1, n) cout << col[i] << " " ; cout << endl ;
dijkstra() ;
printf("%lld
", dis[col[n]]) ;
return 0 ;
}