生活随笔
收集整理的這篇文章主要介紹了
CF 221 C Circling Round Treasures - dp - 状压
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
題目大意：
給你一張網(wǎng)個圖，每個位置是空地、障礙、炸彈、寶藏、起點之一。
規(guī)劃一條從其點出發(fā)不包含炸彈的閉合路線（回路），并可獲得最大的利潤。
利潤定義為路線內部的寶藏收益（可能為負數(shù)）之和減去路徑長度（可以不走）。注意路線可以自交。
為了確定一個格子是否在這條路線里面，請使用以下算法判斷：1.假設該點的坐標為需要判斷的點為 p(i,j) ，該點不在路線上。2.從該點往任意方向作一條射線，如果與路線相交奇數(shù)次，我們就認為這個格子在這條路線里面，否則這個格子在這條路線外面。
n,m≤20,t≤8,∣value∣≤200n,m\le20,t\le8,|value|\le200n,m≤20,t≤8,∣value∣≤200，其中ttt為寶藏和障礙的數(shù)量之和。
題解：
考慮dp（雖然最后不需要），顯然你會設dp(x,y,s)表示現(xiàn)在在(x,y)，已經(jīng)收集了恰好s這個集合的寶藏的最短路。發(fā)現(xiàn)不能確定s的轉移，gg。
然后意識到對于一個寶藏的判定等價于引出一條射線并判定交點個數(shù)奇偶，然后欽定所有射線的方向（我是欽定了上偏右60度角），然后狀壓這個奇偶性，最后bfs一波確定每個狀態(tài)的值即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<climits>
#include<cmath>
#include<assert.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define INF (INT_MAX/20-10)
#define inf (INT_MIN/20+10)
#define MXA 23
#define MXS 280
#define N MXA*MXA*MXS
#define M (N*4)
#define db double
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
using namespace std
;
const db sqrt3
=sqrt(3);
struct edges
{int to
,pre
;
}e
[M
];int h
[N
],etop
,id
[MXA
][MXA
][MXS
],d
[N
],a
[MXA
][MXA
];queue
<int> q
;
inline int add_edge(int u
,int v
) { return e
[++etop
].to
=v
,e
[etop
].pre
=h
[u
],h
[u
]=etop
; }
struct P
{int x
,y
,val
;P(int _x
=0,int _y
=0,int _v
=0){ x
=_x
,y
=_y
,val
=_v
; }
}p
[30];int dx
[4]={0,1,0,-1},dy
[4]={1,0,-1,0};
inline int bfs(int s
,int n
)
{while(!q
.empty()) q
.pop();for(int i
=1;i
<=n
;i
++) d
[i
]=INF
;d
[s
]=0,q
.push(s
);while(!q
.empty()){int x
=q
.front();q
.pop();for(int i
=h
[x
],y
;i
;i
=e
[i
].pre
)if(d
[y
=e
[i
].to
]==INF
) d
[y
]=d
[x
]+1,q
.push(y
);}return 0;
}
struct V
{db x
,y
;V(db _x
=0,db _y
=0) { x
=_x
,y
=_y
; }
};
inline db
cross(const V
&a
,const V
&b
) { return a
.x
*b
.y
+a
.y
*b
.x
; }
inline int sgn(db x
) { return (x
<0)?-1:(x
>0); }
int main()
{int n
,m
,ans
=0,sx
=0,sy
=0;int nc
=0;scanf("%d%d",&n
,&m
);for(int i
=1;i
<=n
;i
++){static char s
[MXA
];scanf("%s",s
+1);for(int j
=1;j
<=m
;j
++)if(s
[j
]=='S') sx
=i
,sy
=j
,a
[i
][j
]=0;else if(s
[j
]=='#') a
[i
][j
]=1;else if(s
[j
]=='.') a
[i
][j
]=0;else if(s
[j
]=='B') a
[i
][j
]=3;else p
[s
[j
]-'1']=P(i
,j
,0),nc
=max(nc
,s
[j
]-'0'),a
[i
][j
]=2;}for(int i
=0;i
<nc
;i
++) scanf("%d",&p
[i
].val
);rep(i
,1,n
) rep(j
,1,m
) if(a
[i
][j
]==3) p
[nc
++]=P(i
,j
,inf
);int all
=(1<<nc
)-1,c
=0;rep(i
,1,n
) rep(j
,1,m
) rep(s
,0,all
) id
[i
][j
][s
]=++c
;rep(s
,0,all
) rep(i
,1,n
) rep(j
,1,m
) rep(k
,0,3){if(a
[i
][j
]) continue;int x
=i
+dx
[k
],y
=j
+dy
[k
],t
=s
;if(x
<=0||x
>n
||y
<=0||y
>m
||a
[x
][y
]) continue;rep(q
,0,nc
-1){int px
=p
[q
].x
,py
=p
[q
].y
;V
v1(px
-i
,j
-py
),v2(px
-x
,y
-py
),v3(1,sqrt3
);int s1
=sgn(cross(v3
,v1
)),s2
=sgn(cross(v3
,v2
));if(s1
!=s2
&&py
<=min(j
,y
)) t
^=(1<<q
);}add_edge(id
[i
][j
][s
],id
[x
][y
][t
]);
}bfs(id
[sx
][sy
][0],c
);for(int s
=0,v
;s
<=all
;ans
=max(ans
,v
-d
[id
[sx
][sy
][s
]]),s
++)for(int i
=v
=0;i
<nc
;i
++) if((s
>>i
)&1) v
+=p
[i
].val
;return !printf("%d\n",ans
);
}
總結
以上是生活随笔為你收集整理的CF 221 C Circling Round Treasures - dp - 状压的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。
