Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
又是个简单dp 1AC 【3428K 141MS】#include <iostream> using namespace std; int pow6[5] = {1, 6, 36, 216, 1296}; int dp[100][8000] = {0}; int main() { int b; int idx[1000]; int gs[5], price[5]; cin >> b; for(int i = 0; i < b; i++){ int aa, bb, cc; cin >> aa >> bb >> cc; idx[aa] = i; gs[i] = bb; price[i] = cc; } int so[100][5] = {{0}}; int soprice[100]; int soNum; cin >> soNum; for(int i = 0; i < soNum; i++){ int zs; cin >> zs; for(int j = 0; j < zs; j++){ int bh, ggs; cin >> bh >> ggs; so[i][idx[bh]] = ggs; } int pr; cin >> pr; soprice[i] = pr; } if(b == 0){ cout << 0 << endl; return 0; } int mxSt = 0; for(int i = 0; i < b; i++){ mxSt += pow6[i] * gs[i]; } //cout << mxSt << endl; bool valid[8000] = {false}; int wei[8000][5]; for(int i = 0; i <= mxSt; i++){ //int stt[5]; for(int j = 0; j < b; j++){ //stt[j] = (mxSt/pow6[j])%6; wei[i][j] = (i/pow6[j])%6; } valid[i] = true; for(int j = 0; j < b; j++){ if(wei[i][j] > gs[j]){ valid[i] = false; break; } } } for(int i = 0; i <= mxSt; i++){ if(!valid[i]) continue; dp[0][i] = 0; for(int j = 0; j < b; j++){ dp[0][i] += wei[i][j] * price[j]; } } //for(int i = 0; i <= mxSt; i++) cout << valid[i] << " "; cout << endl; //for(int i = 0; i <= mxSt; i++) cout << dp[0][i] << " "; cout << endl; for(int i = 1; i <= soNum; i++){//使用第i-1个so int ii = i-1; for(int j = 0; j <= mxSt; j++){//状态数为j if(!valid[j]) continue; int Mx = 2147483647; for(int k = 0; k < b; k++){ if(so[ii][k] == 0) continue; int temp = wei[j][k] / so[ii][k]; if(temp < Mx) Mx = temp; } if(Mx == 0){ dp[i][j] = dp[i-1][j]; continue; } int tempRes = dp[i-1][j]; for(int k = 1; k <= Mx; k++){ int stateVal = j; for(int l = 0; l < b; l++){ stateVal -= k * pow6[l] * so[ii][l]; } int tmp = k * soprice[ii] + dp[i-1][stateVal]; if(tmp < tempRes) tempRes = tmp; } dp[i][j] = tempRes; } } cout << dp[soNum][mxSt] << endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator