$$\Huge版权声明$$
原作者为 Conan15。
$$\Huge转载请注明出处。$$
$$\Huge 原帖戳这里$$
温馨提示：此题解适合人群为算法学习者，不那么适合语法基础课还没学完的学生，对于初学者，建议看看yxc视频
由于原帖的 markdown die 码超过 10w 字符了写不下，
所以又开了一个……
正文继续！
算法一百零六、缩点
感谢 @Shine_Cai 提供思路。
原理：给定一个 n 个点 m 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大，可以用缩点做。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 15, M = 2e5 + 10;
vector<int> edge[N];
int h[N], e[M], ne[M], idx, p[N];
int in[N];
int n, m;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
in[b]++;
}
int dfn[N], low[N], tot = 0;
stack<int> stk;
bool st[N];
int sz[N], scc[N], color;
void tarjan(int u) {
dfn[u] = low[u] = ++tot;
stk.push(u); st[u] = true;
for (int v : edge[u]) {
if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if (st[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
++color;
while (stk.top() != u) {
scc[stk.top()] = color;
st[stk.top()] = false; stk.pop();
}
scc[stk.top()] = color;
st[stk.top()] = false; stk.pop();
}
}
queue<int> q;
int dp[N];
void topsort() {
for (int i = 1; i <= color; i++) {
dp[i] = sz[i];
if (in[i] == 0) q.push(i);
}
while (q.size()) {
int u = q.front(); q.pop();
for (int i = h[u]; ~i; i = ne[i]) {
int v = e[i];
dp[v] = max(dp[v], dp[u] + sz[v]); in[v]--;
if (in[v] == 0) q.push(v);
}
}
int ans = 0;
for (int i = 1; i <= color; i++) ans = max(ans, dp[i]);
printf("%d\n", ans);
}
int main() {
memset(h, -1, sizeof h);
n = 2, m = 1;
for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
while (m--) {
int a = 1, b = 2;
edge[a].push_back(b);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; i++) {
sz[scc[i]] += p[i];
for (int j : edge[i])
if (scc[i] != scc[j]) add(scc[i], scc[j]);
}
topsort();
return 0;
}
算法一百零七、A* 算法（k 短路）
感谢 [@Hugo_Von] 同学的贡献。
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
const int amou=1e3+90,M=2e4+90;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
int head[amou],hh[amou],nxt[M],ver[M],cnt,edge[M];
bool we[amou];
int H[amou],times[amou];
int n,m,k,S,T;
void add(int head[],int a,int b,int c){
nxt[++cnt]=head[a],head[a]=cnt,ver[cnt]=b,edge[cnt]=c;
}
void Dijkstra(){
priority_queue<PII,vector<PII>,greater<PII> >kl;
kl.push({0,T});
memset(H,0x3f,sizeof H);
H[T]=0;
while(!kl.empty())
{
PII tou=kl.top();
kl.pop();
int i=tou.y;
if(we[i]) continue;
we[i]=1;
for(int io=hh[i];io;io=nxt[io])
{
int v=ver[io];
if(H[v]>H[i]+edge[io])
{
H[v]=H[i]+edge[io];
kl.push({H[v],v});
}
}
}
}
void Astar(){
priority_queue<PIII,vector<PIII>,greater<PIII> >kl;
kl.push({H[S],{0,S}});
while(!kl.empty())
{
PIII tou=kl.top();
kl.pop();
int i=tou.y.y,G=tou.y.x;
times[i]++;
if(i==T)
{
if(times[T]==k)
{
cout<<G;
return;
}
continue;
}
for(int io=head[i];io;io=nxt[io])
{
int v=ver[io];
if(times[v]<k)
kl.push({edge[io]+G+H[v],{edge[io]+G,v}});
}
}
}
int main(){
n=3,m=3,k=2;
S=n,T=1;
int one,two;
cin>>one>>two;
add(head,3,2,one);
add(hh,2,3,one);
add(head,2,1,two);
add(hh,1,2,two);
add(head,3,1,0);
add(hh,1,3,0);
Dijkstra();
Astar();
return 0;
}
算法一百零八、三分
用顶点式 $y=a(x-h)^2+k$
感谢 [@Hugo_Von] 同学的贡献。
#include<bits/stdc++.h>
using namespace std;
int a,b;
long long f(int x){
return (long long)(x-a-b)*(x-a-b);
}
int main(){
cin>>a>>b;
int l=-1,r=1000000000;
while(l+1<r){
int mid1=l+(r-l)/3,mid2=mid1+(r-l)/3;
if(f(mid1)>f(mid2)) l=mid1;
else r=mid2;
}
cout<<l+1;
return 0;
}
算法一百零九、扫描线算法（矩形面积并）
感谢 [@Hugo_Von] 同学的贡献。
#include<bits/stdc++.h>
using namespace std;
long long ans;
long long n;
long long xa,xb,ya,yb;
long long y[210000];
struct smx{
long long ya,yb,x,mark;
}line[210000];
bool cmp(smx a,smx b){return a.x<b.x;}
struct node{
long long c,tag;
}tr[810000];
void pushup(long long num,long long l,long long r) {
if(!tr[num].tag){
if(l==r)tr[num].c=0;
else tr[num].c=tr[num<<1].c+tr[num<<1|1].c;
}
}
void change(long long num,long long l,long long r,long long ya,long long yb,long long k){
if(ya<=l&&r<=yb){
tr[num].tag+=k;
if(tr[num].tag)tr[num].c=y[r+1]-y[l];
else tr[num].c=0;
pushup(num,l,r);
return ;
}
long long mid=(l+r)>>1;
if(ya<=mid)change(num<<1,l,mid,ya,yb,k);
if(mid+1<=yb)change(num<<1|1,mid+1,r,ya,yb,k);
pushup(num,l,r);
}
int main(){
int one,two;
cin>>one>>two;
n=2;
xa=0,ya=0,xb=1,yb=one;
y[1]=ya;y[2]=yb;
line[1]=(smx){ya,yb,xa,3};line[2]=(smx){ya,yb,xb,-3};
xa=10,ya=0,xb=11,yb=two;
y[3]=ya;y[4]=yb;
line[3]=(smx){ya,yb,xa,3};line[4]=(smx){ya,yb,xb,-3};
n<<=1;
sort(y+1,y+n+1);
sort(line+1,line+n+1,cmp);
int len=unique(y+1,y+n+1)-(&y[1])-1;
for(int i=1;i<n;i++){
ya=lower_bound(y+1,y+len+2,line[i].ya)-y;
yb=lower_bound(y+1,y+len+2,line[i].yb)-y-1;
change(1,1,len,ya,yb,line[i].mark);
ans+=tr[1].c*(line[i+1].x-line[i].x);
}
cout<<ans;
return 0;
}
算法一百一十、四边形不等式优化 DP
感谢 @Shine_Cai
//原理：石子合并，但是四边形不等式优化DP
#include<bits/stdc++.h>
using namespace std;
const int N=1009;
int dp[N][N],s[N][N],n,sum[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
n=2;int x;
memset(dp,0x3f,sizeof dp);
for(int i=1; i<=n; i++)
cin>>x,s[i][i]=i,dp[i][i]=0,sum[i]=sum[i-1]+x;
for(int len=2; len<=n; len++){
for(int l=1; l<=n-len+1; l++){
int r=l+len-1;
for(int k=s[l][r-1]; k<=s[l+1][r]; k++)
if(dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]<dp[l][r])
dp[l][r]=dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1],s[l][r]=k;
}
}
cout<<dp[1][n];
return 0;
}
算法一百一十一、分层图
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int inf = INT_MAX;
typedef pair<int, int> PII;
int n, m, k, s, t;
int d[N][11];
struct node
{
int u, v;
};
vector<node> g[N];
bool vis[N];
void dijkstra()
{
priority_queue<PII, vector<PII>, greater<PII> > q;
for(int i = 0;i <= k;i ++ ) d[s][i] = 0;
for(int i = 0;i <= k;i ++ )
{
q.push(make_pair(0, s));
while(q.size())
{
int x = q.top().second; q.pop();
if(vis[x]) continue;
vis[x] = true;
for(int j = 0;j < g[x].size();j ++ )
{
int y = g[x][j].u;
int f = 0;
if(i && d[y][i] > d[x][i - 1])
{
d[y][i] = d[x][i - 1];
f = 1;
}
if(d[y][i] > d[x][i] + g[x][j].v)
{
d[y][i] = d[x][i] + g[x][j].v;
f = 1;
}
if(f == 1) q.push(make_pair(d[y][i], y));
}
}
memset(vis, false, sizeof(vis));
}
}
int main(){
// cin >> n >> m >> k;
// cin >> s >> t;
k = 0;
s = 0, t = 2;
int a, b;
cin >> a >> b;
g[0].push_back({1, a});
g[1].push_back({0, a});
g[1].push_back({2, b});
g[2].push_back({1, b});
n = 3;
// for(int i = 1;i <= m;i ++ )
// {
// int a, b, c;
// cin >> a >> b >> c;
// g[a].push_back({b, c});
// g[b].push_back({a, c});
// }
for(int i = 0;i < n;i ++ )
{
for(int j = 0;j <= k;j ++ )
{
d[i][j] = inf;
}
}
dijkstra();
int ans = inf;
for(int i = 0;i <= k;i ++ ) ans = min(ans, d[t][i]);
cout << ans << endl;
return 0;
}
四边形不等式优化区间DP的代码是有了吗？
没有
麻烦给个这种算法的专题好吗，想了解一下，我还没学
已加入该代码
鄙人不才，但应该写得还算清楚：
https://www.luogu.com.cn/article/itinpgjw
谢谢
我优化了一下你的代码
cpp
#include[HTML_REMOVED]
using namespace std;
const int N = 1009;
int dp[N][N], s[N][N], n, sum[N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
n = 2;
int x;
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= n; i) {
cin >> x;
s[i][i] = i;
dp[i][i] = 0;
sum[i] = sum[i - 1] + x;
}
for (int len = 2; len <= n; len) {
for (int l = 1; l <= n - len + 1; l) {
int r = l + len - 1;
for (int k = s[l][r - 1]; k <= s[l + 1][r]; k) {
if (dp[l][k] + dp[k + 1][r] + sum[r] - sum[l - 1] < dp[l][r]) {
dp[l][r] = dp[l][k] + dp[k + 1][r] + sum[r] - sum[l - 1];
s[l][r] = k;
}
}
}
}
cout << dp[1][n];
return 0;
}
使其时间复杂度从54毫秒变为53毫秒
你或许可以去了解一下时间复杂度是什么？
啊呸，写错了，是运行时间，我知道时间复杂度是形如O（N² ）、O（N log N）之类的东西，一时口误
所以你优化了哪里，除了改一下格式我没看出来哪里更优了？
A*算法（k短路）：
好的，已加入，谢谢您的贡献！
原帖打不开：（
貌似炸了。
啊！？我去看看
你说得对，很不幸的是，。。。你的电脑炸了
我这里可以 awa
哟这不是阔别已久的 2AK 吗？（我没记错吧
是不是还可以补个莫队上去（维护区间和）
要不你写一个（）我最近有点忙没时间写
我也要NOIP呀（
字符串的代码有吗？
这不就是高精。。。
az
我就说这个怎么像什么玩意分层图
@Conan15
收到。
您不是 zky 本人吧你的 at 挂了
不想修了，复习呢随机算法升级版
随机算法,看脸
扫描线算法（矩形面积并）：
已加入
三分（用顶点式$y=a(x−h)^2+k$）
好的，已加入
请问这个算法有什么模板题吗，想去看看（
洛谷P1883
我看不懂，但我大受震撼
？？？？？？
其实就是给你两个点一条边，点权为a和b，然后缩完点跑Top排序求最长路，求出来就是a+b。
嘿嘿由于昨天刚好在练 tarjan 所以 P 了一份自己的 die 码上去（）（）
四边形不等式的做法不叠上去了吗？发在一贴了。
%%%
%%%
你们在楼上吗
三楼
第一间
Orz
打比赛ing.jpg