精彩打脸合集

P3133 [USACO16JAN]Radio Contact G

一道DP，不会推式子，以后要复习

#include <bits/stdc++.h>
using namespace std;
/*

f[i][j] 表示 FJ 第 i 步，BS 第 j 步时的最小花费

可以从以下三种情况转移过来
1. FJ 不动 BS 动
2. FJ 动 BS 不动
3. FJ 不动 BS 不动

f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+dis(i,j);

*/
struct Node {
    int x,y;
}fj[1005],bs[1005];
int n,m,f[1005][1005];
inline int dis(int i,int j) {
    return (fj[i].x-bs[j].x)*(fj[i].x-bs[j].x)+(fj[i].y-bs[j].y)*(fj[i].y-bs[j].y);
}
int main() {
    scanf("%d%d%d%d%d%d",&n,&m,&fj[0].x,&fj[0].y,&bs[0].x,&bs[0].y);
    for(int i=1;i<=n;i++) {
        char c;
        cin>>c;
        if(c=='N')
            fj[i].y=fj[i-1].y+1,fj[i].x=fj[i-1].x;
        else if(c=='S')
            fj[i].y=fj[i-1].y-1,fj[i].x=fj[i-1].x;
        else if(c=='W')
            fj[i].y=fj[i-1].y,fj[i].x=fj[i-1].x-1;
        else if(c=='E')
            fj[i].y=fj[i-1].y,fj[i].x=fj[i-1].x+1;
    }
    for(int i=1;i<=m;i++) {
        char c;
        cin>>c;
        if(c=='N')
            bs[i].y=bs[i-1].y+1,bs[i].x=bs[i-1].x;
        else if(c=='S')
            bs[i].y=bs[i-1].y-1,bs[i].x=bs[i-1].x;
        else if(c=='W')
            bs[i].y=bs[i-1].y,bs[i].x=bs[i-1].x-1;
        else if(c=='E')
            bs[i].y=bs[i-1].y,bs[i].x=bs[i-1].x+1;
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;i++) f[i][0]=f[i-1][0]+dis(i,0);
    for(int i=1;i<=m;i++) f[0][i]=f[0][i-1]+dis(0,i);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f[i][j]=min(f[i-1][j],min(f[i][j-1],f[i-1][j-1]))+dis(i,j);
    printf("%d",f[n][m]);
    return 0;
}

P4779 【模板】单源最短路径（标准版）

复习了dijkstra，还是不熟，多次WA

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
#define fi first
#define se second
#define mp make_pair
const int N = 100005,M = N*2;
int dis[N],book[N],first[N],nxt[M],v[M],w[M],idx,n,m,s,x,y,z;
void add(int x,int y,int z) {
    v[++idx]=y;
    w[idx]=z;
    nxt[idx]=first[x];
    first[x]=idx;
}
void dij() {
    for(int i=1;i<=n;i++) dis[i]=1e10;
    priority_queue<PII> q;
    dis[s]=0;
    q.push(mp(0,s));
    while(!q.empty()) {
        int t=q.top().se;
        q.pop();
        if(book[t]) continue;
        book[t]=1;
        for(int i=first[t];i;i=nxt[i]) {
            if(dis[t]+w[i]<dis[v[i]]) {
                dis[v[i]]=dis[t]+w[i];
                q.push(mp(-dis[v[i]],v[i]));
            }
        }
    }
}//17行挺好打的
int main() {
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)  {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    dij();
    for(int i=1;i<=n;i++) printf("%d ",dis[i]);
    return 0;
}

P2015 二叉苹果树

AC了但确实不会，要复习

#include <bits/stdc++.h>
using namespace std;
/*

f[u][j] 表示以 u 为子树根节点保留 j 条边时的最大苹果数
son[u][0] 表示 u 的左儿子，son[u][1] 表示 u 的右儿子
apple[u][0] 表示 u与 u 的左儿子连边的苹果数，apple[u][1] 表示 u与 u 的右儿子连边的苹果数

用 k 表示保留给以 u 为根节点的子树中分配给 u 的左节点能够保留的边
1. k==0，干掉左子树，探寻右子树的情况
2. k==j，干掉右子树，探寻左子树的情况
3. k>0&&k<j，给左子树 k 条边，右子树 j-k 条边
（实际上如果要保留一棵子树就必定与根节点连有边，所以边的数量-1）

1. f[u][j]=max(f[u][j],f[son[u][1]][j-1]+apple[u][1]);
2. f[u][j]=max(f[u][j],f[son[u][0]][j-1]+apple[u][0]);
3. f[u][j]=max(f[u][j],f[son[u][0]][k-1]+apple[u][0]+f[son[u][1]][j-k-1]+apple[u][1]);

思路：
    1. 边权转点权
    2. 树形DP
*/
const int N=105,M=N*2;
int n,q,idx;
int first[N],nxt[M],v[M],w[M];
int son[N][2],apple[N][2],f[N][N];
void add(int x,int y,int z) {
    v[++idx]=y;
    w[idx]=z;
    nxt[idx]=first[x];
    first[x]=idx;
}
int dfs(int u,int father) {
    int idx2=0;
    for(int i=first[u];i;i=nxt[i]) {
        if(v[i]!=father) {
            son[u][idx2]=v[i];//找儿子
            apple[u][idx2]=w[i];//苹果个数
            idx2++;
            dfs(v[i],u);
        }
    }
    for(int j=1;j<=q;j++) {
        for(int k=0;k<=j;k++) {
            if(k==0)
                f[u][j]=max(f[u][j],f[son[u][1]][j-1]+apple[u][1]);
            //1个都不留的情况，由于本身与根节点有一条边，另一个只能是j-1
            else if(k==j)
                f[u][j]=max(f[u][j],f[son[u][0]][j-1]+apple[u][0]);
            //all in
            else
            f[u][j]=max(f[u][j],f[son[u][0]][k-1]+apple[u][0]+f[son[u][1]][j-k-1]+apple[u][1]);
        }
    }
}
int main() {
    scanf("%d%d",&n,&q);
    for(int i=1,x,y,z;i<n;i++) {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    dfs(1,0);
    printf("%d",f[1][q]);
    return 0;
}