【yukicoder】No.90 品物の並び替え
yukicoderさんの問題
参考書
難しさ(初心者目線)
・考え方*
・実装**
・面白さ*
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> using namespace std; #define ll long long #define PI acos(-1.0) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) //方針 //Nが小さいので順列を全探索しても9!=362880パターン=4*10^5くらい //得られる点数は2重ループで計算する.(計算量はM*M/2) //ギリギリ?? //->N=9M=66で14msだった int main(){ int N, M; cin >> N >> M; //点数を保存score[後][前] int score[N][N]; //memset(score, 0, sizeof(score)); FOR(i, 0, N) FOR(j, 0, N) score[i][j] = 0; FOR(i, 0, M){ int item1, item2, tmpscore; cin >> item1 >> item2 >> tmpscore; score[item2][item1] = tmpscore; } //全探索0~N-1の並び替え vector<int> v; FOR(i, 0, N) v.push_back(i); int ans = 0; do{ int ret = 0; //v[usiro]が後ろにある数字v[mae]が前にある数字 //なのでそれをscoreの配列に入れて点数を調べる FOR(usiro, 1, N) FOR(mae, 0, usiro) ret += score[v[usiro]][v[mae]]; ans = max(ans, ret); }while(next_permutation(v.begin(), v.end())); cout << ans << endl; }
コメント
Nが小さかったので全探索ができた.
並び替えはdo{処理}while(next_permutation(並び替えたいvector.begin(), vector.end()));でできる.