Skip to main content
本文の改善
ソース リンク
cubick
  • 2.1万
  • 5
  • 27
  • 64

ビットDPDPの思考回路について

以下のコードのアルゴリズムの思考回路がよくわかりません。

ビット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

ビットDPの思考回路について

#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

ビットDPの思考回路について

以下のコードのアルゴリズムの思考回路がよくわかりません。

ビット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の思考回路について

#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