2020-03-14 13:00:00 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> #define ALL(A) (A).begin(), (A).end() #define ll long long #define rep(i, n) for (int i = 0; i < (n); i++) using namespace std; template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } int dx[] = { 0, 1, -1, 0, 1, -1, 1, -1 }; // i<4:4way i<8:8way int dy[] = { 1, 0, 0, -1, 1, -1, -1, 1 }; const ll mod = 1e9 + 7; const ll INF = -1 * ((1LL << 63) + 1); const int inf = -1 * ((1 << 31) + 1); ll dp[155][15][80]; // dp[i][j][k] := i行目にj番目の石にm回の飛ばしで行く時の最小値 int main(void){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); rep(a,155)rep(b,15)rep(c,80)dp[a][b][c] = 1e7; int n,m,k; cin >> n >> m; vector<vector<pair<int,int>>> x(n); // x[i][j] := i行目のj番目の石の{位置,スコア} rep(i,n){ cin >> k; rep(j,k){ int p,s; cin >> p >> s; x[i].push_back({p,s}); } } // 初期化する // 0行目の石に移る時のスコアは0 rep(j,x[0].size()){ dp[0][j][0] = 0; } rep(i,n){ // c回1行飛ばしを使った事を考える rep(c,m+1){ // i行目のj番目の石について rep(j,x[i].size()){ ll nowp = x[i][j].first; ll nows = x[i][j].second; // 1行だけ飛ぶ場合 rep(a,x[i+1].size()){ // i+1行目のa番目の石について考えます ll nextp = x[i+1][a].first; ll nexts = x[i+1][a].second; chmin(dp[i+1][a][c], dp[i][j][c] + (nows+nexts)*abs(nowp-nextp)); } // 1行飛ばしをする場合 rep(a,x[i+2].size()){ ll nextp = x[i+2][a].first; ll nexts = x[i+2][a].second; chmin(dp[i+2][a][c+1], dp[i][j][c] + (nows+nexts)*abs(nowp-nextp)); } cout << i << " " << c << endl; } } } ll ans = 1e18; rep(i,x[n-1].size()){ rep(a,m+1){ chmin(ans,dp[n-1][i][a]); } } rep(i,x[n-2].size()){ rep(a,m){ chmin(ans,dp[n-2][i][a]); } } cout << ans << endl; }
RECOMMEND