問題概要
個の街があり,その内の幾つかの街に商品を売りに行く.商品の情報は 2 つの配列 で与えられ, 番の商品は,街 で売ることができて,そのときの利益が であることを表す.商品を売りに行く街の訪問順序は予め決まっている.その情報は配列 で与えられ, 番目に訪問する街が である.また,ある商品は高々 1 回しか売ることはできず,ある街への 1 回の訪問では高々 1 つの商品しか売ることはできない.
得られる利益の総和の最大値を求めよ.
解法
商品を売れる街が決まっているので,売れる街が異なる商品については独立に考えることができます.
ある街での判断について考えます.前提として,商品が残っているならば,売らないという選択は明らかに損です,そのことを踏まえると,街への訪問回数とその街で売れる商品の数の内で小さい方を としたとき,そこで売れる商品の内,収入が大きいものから順に 個の商品を売るのが最適な戦略となります.
あとは,全ての街についてこの戦略をシミュレートして,利益の総和を計算すれば問題を解くことができます.
コード
using VI = vector< int >; using VVI = vector< VI >; #define REP2( i, n ) for ( int i = 0; i < ( int )( n ); ++i ) #define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define GET_REP( a, b, c, F, ... ) F #define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ ) #define FOR( e, c ) for ( auto &e : c ) #define ALL( c ) ( c ).begin(), ( c ).end() #define SZ( v ) ( (int)( v ).size() ) #define PB push_back class TravellingSalesmanEasy { public: int getMaxProfit( int M, vector <int> profit, vector <int> city, vector <int> visit ) { const int N = profit.size(); { auto f = bind( minus< int >(), _1, 1 ); transform( ALL( city ), city.begin(), f ); transform( ALL( visit ), visit.begin(), f ); } VVI profits( M ); REP( i, N ) { profits[ city[i] ].PB( profit[i] ); } for_each( ALL( profits ), []( VI &v ){ sort( ALL( v ), greater< int >() ); } ); VI counts( M ); for_each( ALL( visit ), [&]( const int v ){ ++counts[v]; } ); int res = 0; REP( v, M ) { const int m = min( SZ( profits[v] ), counts[v] ); res += accumulate( profits[v].begin(), profits[v].begin() + m, 0 ); } return res; } };