以下のコードのアルゴリズムの思考回路がよくわかりません。
ビットDPを使っているらしいのですが、どういう風にビット演算子を使うとDPになるのか原理が分かりません(なぜDPが成立するのかがわからない)。
また、どのようにすればこのような思考でコードをかけるのでしょうか?
どなたか分かる方はいらっしゃるでしょうか?
コード元: 第16回日本情報オリンピック 予選4
#include<stdio.h>
#include<algorithm>
using namespace std;
int p[110000];
int sum[20][110000];
int sz[20];
int dp[1<<20];
int main(){
int a,b;scanf("%d%d",&a,&b);
for(int i=0;i<a;i++){
scanf("%d",p+i);
p[i]--;
sum[p[i]][i+1]++;
sz[p[i]]++;
}
for(int i=0;i<b;i++)for(int j=0;j<a;j++){
sum[i][j+1]+=sum[i][j];
}
for(int i=0;i<(1<<b);i++)dp[i]=999999999;
dp[0]=0;
for(int i=0;i<(1<<b);i++){
int pos=0;
for(int j=0;j<b;j++)if(i&(1<<j))pos+=sz[j];
for(int j=0;j<b;j++){
if(i&(1<<j))continue;
dp[i+(1<<j)]=min(dp[i+(1<<j)],dp[i]+sz[j]-sum[j][pos+sz[j]]+sum[j][pos]);
}
}
printf("%d\n",dp[(1<<b)-1]);
}
このコードのアルゴリズムの思考回路がよくわかりません
ビットDPを使っているらしいのですが
どういう風にビット演算子を使うとDPになる原理が分かりません
(なぜDPが成立するのかがわからない)
また、どのようにすればこのような思考でコードをかけるのでしょうか?
どなたか分かる方はいらっしゃるでしょうか?
コード元第16回日本情報オリンピック 予選4