CF 580 D Kefa And Dishes 상 압 DP
1308 단어 DPCodeforces대충 하 다
k 개 보너스 가 있 습 니 다. 아 이 템 x 가 아 이 템 y 앞 에 있 으 면 총 가치 + a [x] [y]
m < = n < = 18, 0 < = a [i], c [x] [y] < = 1e9. 선택 할 수 있 는 최대 가 치 는?
폭력 dfs O (C (n, m) * m!) TLE....
그림 (i - > j) 의 변 권 치 는 (a [i] + c [i] [j]) 입 니 다.
지금 은 길이 가 m - 1 이 고 가중치 가 가장 큰 경 로 를 찾 습 니 다.
뚜렷 한 상 압. dp [s] [u] 를 설정 하면 u 점 을 표시 하고 지나 간 점 의 상 태 는 s 입 니 다.
dp[s][u] + a[j]+c[u][j] -> dp[s|2^j][j] (u 는 s 에 있 고 j 는 더 이상 s 가 아니다)
res=max(res, dp[s][i] (i=1..n && bit(s)==m))
#include
using namespace std;
typedef long long ll;
const int N=19;
int n,m,k;
ll a[N],b[N][N];
ll dp[1<>n>>m>>k;
for(int i=0;i>a[i];
while(k--)
{
ll u,v,x;
cin>>u>>v>>x;
u--,v--;
b[u][v]=x;
}
for(int i=0;i>j)&1))
continue;
for(int k=0;k>k)&1)
continue;
dp[i|(1<>j)&1)
cnt++;
if(cnt==m)
{
for(int j=0;j 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[BOJ]11048(python)python 풀이 DP를 이용해 풀이 보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서 고민을 했는데 이 문구 덕분에 DP 를 이용해 풀이할 수 있었다 뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
