結果

問題 No.90 品物の並び替え
ユーザー kongarishisyamo
提出日時 2016-05-01 21:59:31
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 5,000 ms
コード長 1,033 bytes
コンパイル時間 593 ms
コンパイル使用メモリ 60,124 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-05 00:54:28
合計ジャッジ時間 1,229 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<cmath>
using namespace std;
#define MAX ((2<<9)+1)
#define INF -1000000000
int bitdp[MAX];
int data[9][9];
void dp(int bit,int n){
    bool f[9];
    for(int i=0;i<n;i++){
        if((bit>>i)%2==0) f[i]=false;
        else f[i]=true;
    }
    for(int i=0;i<n;i++){
        if((bit>>i)%2==1){
            int tmpbit=bit;
            tmpbit-=pow(2.0,i);
            int c=bitdp[tmpbit];
            int pc=0;
            for(int j=0;j<n;j++){
                if(!f[j]) pc+=data[i][j];
            }
            //cout<<bit<<","<<i<<","<<bitdp[bit]<<","<<c<<","<<pc<<endl;
            bitdp[bit]=max(bitdp[bit],c+pc);
        }
    }
}
void make(int n,int c,int bit,int deep,int to,int N){
    if(n==0){
        if(to==c){
            dp(bit,N);
        }
    }
    else{
        if(to!=c) make(n-1,c+1,bit+pow(2.0,deep),deep+1,to,N);
        make(n-1,c,bit,deep+1,to,N);
    }
}
int main(){
    int N,M;
    int item1,item2,score;
    cin>>N>>M;
    for(int i=0;i<M;i++){
        cin>>item1>>item2>>score;
        data[item1][item2]=score;
    }
    for(int i=0;i<=(2<<9);i++) bitdp[i]=INF;
    bitdp[0]=0;
    for(int i=1;i<=N;i++){
        make(N,0,0,0,i,N);
    }
    cout<<bitdp[(int)pow(2.0,N)-1]<<endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0