最后一战の板子
谜之soul_北冥X
2020-12-03 20:06:21
# ~~AFO前的挣扎~~
# DP
## 01背包
```cpp
//无优化
for(int i=1;i<=n;i++)
{
for(int c=0;c<=m;c++)
{
f[i][c]=f[i-1][c];
if(c>=w[i])
f[i][c]=max(f[i][c],f[i-1][c-w[i]]+v[i]);
}
}
//一位数组优化
for(int i=1;i<=n;i++)
{
for(int c=m;c>=0;c--)
{
if(c>=w[i])
f[c]=max(f[c],f[c-w[i]]+v[i]);
}
}
//常数优化
for(int i=1;i<=n;i++)
{
sumw+=w[i];
bound=max(m-sumw,w[i]);
for(int c=m;c>=bound;c--)
{
if(c>=w[i])
f[c]=max(f[c],f[c-w[i]]+v[i]);
}
}
```
## 完全背包
```cpp
for(int i=1;i<=n;i++)
{
for(int c=0;c<=m;c++)
{
if(c>=w[i])
f[c]=max(f[c],f[c-w[i]]+v[i]);
}
}
```
## 多重背包
```cpp
for(int i=1;i<=n;i++)
{
if(w[i]*a[i]>m)
{
for(int c=0;c<=m;c++)
{
if(c>=w[i])
f[c]=max(f[c],f[c-w[i]]+v[i]);
}
}
else
{
k=1;amount=a[i];
while(k<amount)
{
for(int c=k*w[i];c>=0;c--)
{
if(c>=w[i])
f[c]=max(f[c],f[c-w[i]]+k*v[i]);
}
amount-=k;
k<<=1;
}
for(int c=amount*w[i];c>=0;c--)
{
f[c]=max(f[c],f[c-w[i]]+amount*v[i]);
}
}
}
```
## 带有附件的01背包
```cpp
for(int i=1;i<=m;i++){// read
int a,b,c;
a=read();
b=read();
c=read();
if(c==0){ //无附件
zw[i]=a;
zv[i]=a*b;
}
else{ //有附件
fw[c][0]++;
fw[c][fw[c][0]]=a;
fv[c][fw[c][0]]=a*b;
}
}
for(int i=1;i<=m;i++){
for(int j=n;j>=zw[i]&&zw[i]!=0;j--){
dp[j] = max(dp[j],dp[j-zw[i]]+zv[i]);
if(j >= zw[i]+fw[i][1])
dp[j] = max(dp[j],dp[j-zw[i]-fw[i][1]]+zv[i]+fv[i][1]);
if(j >= zw[i]+fw[i][2])
dp[j] = max(dp[j],dp[j-zw[i]-fw[i][2]]+zv[i]+fv[i][2]);
if(j >= zw[i]+fw[i][1]+fw[i][2])
dp[j] = max(dp[j],dp[j-zw[i]-fw[i][1]-fw[i][2]]+zv[i]+fv[i][2]+fv[i][1]);
}
}
```
## 最长上升子序列(n log n)
```cpp
dp[1]=h[1];
for(int i=2;i<=cnt;i++)
{
if(dp[len]>=h[i]) dp[++len]=h[i];
else{
int a=upper_bound(dp+1,dp+1+len,h[i])-dp;
dp[a]=h[i];
}
```
# 图论
## 存图
```cpp
//邻接矩阵（有向图）
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
mapp[u][v]=w;
}
//边集数组（有向图）
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
e[i].u=u;
e[i].v=v;
e[i].dis=w;
}
//链式前向星 （有向图）
void addedge(int u,int v,int w){
e[cnt].to=v;
e[cnt].dis=w;
e[cnt].next=h[u];
h[u]=++cnt;
}
```
## 最短路
```cpp
//Floyd
for(int k=0;k<n;k++){ //k为中间节点
for(int i=0;i<n;i++) //i为起点
for(int j=0;j<n;j++) //j为终点
if(i!=k&&i!=j&&k!=j)
if(arr[i][k]+arr[k][j]<arr[i][j])
arr[i][j]=arr[i][k]+arr[k][j];
}
//Dijkstra
void dijkstra(int k){
dis[k]=0;
q.push((node){0,k});
while(!q.empty()){
node tp=q.top();
int x=tp.pos;
int d=tp.dis;
q.pop();
if(vis[x]==1)
continue;
vis[x]=1;
for(int i=h[x];i;i=e[i].next){
int y=e[i].to;
if(dis[y]>dis[x]+e[i].dis){
dis[y]=dis[x]+e[i].dis;
q.push((node){dis[y],y});
}
}
}
}
```
## 最小生成树
```cpp
//kruskal
int find(int x){
while(x!=f[x])
x=f[x]=f[f[x]];
return x;
}
bool cmp(edge a,edge b){
return a.w<b.w;
}
void kruskal(){
for(int i=1;i<=1001;i++)
f[i]=i;
int cnt=0;
sort(e+1,e+1+m,cmp);
for(int i=1;i<=m;i++){
int ev,eu;
ev=find(e[i].v);
eu=find(e[i].u);
if(ev==eu)
continue;
tot+=e[i].w;
f[eu]=ev;
if(++cnt==n-1)
break;
}
return;
}
//prim
priority_queue<node> myq;
void pulimu(){
int cc=0;
dis[1]=0;
myq.push((node){0,1});
while(!myq.empty()&&cc<n){
node temp=myq.top();
myq.pop();
int x=temp.pos;
int d=temp.dis;
if(vis[x]==1)
continue;
vis[x]=1;
cc++;
ans+=d;
for(int i=h[x];i;i=e[i].next){
if(dis[e[i].to]>e[i].dis){
dis[e[i].to]=e[i].dis;
myq.push((node){dis[e[i].to],e[i].to});
}
}
}
return;
}
```