#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 ][1] [1]: https://www.ioi-jp.org/joi/2016/2017-yo/2017-yo-t4/review/2017-yo-t4-review.html