[USACO 2016 Dec Gold] Tutorial-白红宇

[USACO 2016 Dec Gold] Tutorial

阅读量：5140 次

发布时间：2019-06-13

本文共 2947 字，大约阅读时间需要 9 分钟。

Link:

A:

贪心从小到大插入，用并查集维护连通性

#include 
      
       using namespace std;#define X first#define Y secondtypedef double db;typedef long long ll;typedef pair
       
         P;const int MAXN=1e3+10;int n,tot,cnt,f[MAXN];P dat[MAXN];struct edge{
    int x,y;ll w;}e[MAXN*MAXN];ll sqr(int x){
    return 1ll*x*x;}bool cmp(edge x,edge y){
    return x.w

Problem A

B:

$dp[1...n][1...m][0/1]$，其中0/1表示当前在哪一边

#include 
      
       using namespace std;#define X first#define Y secondtypedef double db;typedef long long ll;typedef pair
       
         P;const int MAXN=1e3+10,INF=0x3f3f3f3f;ll dp[MAXN][MAXN][2];int n,m;P dat[MAXN*2];ll sqr(int x){
    return 1ll*x*x;}ll dist(int a,int b){
    return sqr(dat[a].X-dat[b].X)+sqr(dat[a].Y-dat[b].Y);}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n+m;i++)        scanf("%d%d",&dat[i].X,&dat[i].Y);        memset(dp,0x3f,sizeof(dp));    dp[1][0][0]=0;    for(int i=0;i<=n;i++)        for(int j=0;j<=m;j++)            for(int k=0;k<2;k++)            {                if(i) dp[i+1][j][0]=min(dp[i+1][j][0],dp[i][j][0]+dist(i,i+1));                if(j) dp[i+1][j][0]=min(dp[i+1][j][0],dp[i][j][1]+dist(n+j,i+1));                if(i) dp[i][j+1][1]=min(dp[i][j+1][1],dp[i][j][0]+dist(i,n+j+1));                if(j) dp[i][j+1][1]=min(dp[i][j+1][1],dp[i][j][1]+dist(n+j,n+j+1));            }    printf("%lld",dp[n][m][0]);    return 0;}

Problem B

C:

可以明显发现是最短路模型，但如果将一个点能不转弯走到的所有点的边都连上明显$TLE$

那么在跑最短路时多记录一维当前方向即可，每次转移判断是否要转向来决定是否增加代价

这样只要与不穿过其他点就能到达的点连边就行了

#include 
      
       using namespace std;#define X first#define Y secondtypedef double db;typedef long long ll;typedef pair
       
         P;const int MAXN=1e5+10,INF=0x3f3f3f3f;int n,x,y,h1[MAXN],h2[MAXN],dist[MAXN][2],tot; struct edge{
    int nxt,to;}e1[MAXN<<2],e2[MAXN<<2];struct node{
    int x,y,id;}tmp[MAXN],dat[MAXN];struct Queue{
    int w,x,dir;};bool cmp1(node a,node b){
    return a.x
        
         b.w;}void add1(int x,int y){    e1[++tot]={h1[x],y};h1[x]=tot;    e1[++tot]={h1[y],x};h1[y]=tot;}void add2(int x,int y){    e2[++tot]={h2[x],y};h2[x]=tot;    e2[++tot]={h2[y],x};h2[y]=tot;}priority_queue
         
           q;int main(){    scanf("%d",&n);n+=2;    scanf("%d%d",&x,&y);dat[1]=tmp[1]={x,y,1};    scanf("%d%d",&x,&y);dat[n]=tmp[n]={x,y,n};    for(int i=2;i
          
           dist[t.x][t.dir]+(t.dir!=0))                dist[e1[i].to][0]=dist[t.x][t.dir]+(t.dir!=0),q.push(Queue{dist[e1[i].to][0],e1[i].to,0});        for(int i=h2[t.x];i;i=e2[i].nxt)            if(dist[e2[i].to][1]>dist[t.x][t.dir]+(t.dir!=1))                dist[e2[i].to][1]=dist[t.x][t.dir]+(t.dir!=1),q.push(Queue{dist[e2[i].to][1],e2[i].to,1});    }    int res=min(dist[n][0],dist[n][1]);    printf("%d",res==INF?-1:res);    return 0;}