It’s a bottom up dp approach.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 |
#include <iostream> #include <cstdio> #include <queue> #include <sstream> #include <string> #include <queue> #include <vector> #include <cstring> #include <algorithm> #include <cmath> #define INF 100000000 using namespace std; vector<int> vb[11]; vector<int> v; int dp[11][1010]; void init() { for(int i=0;i<11;i++) { vb[i].clear(); for(int j=0;j<1010;j++) { dp[i][j]=-1; } } } int _min(int a,int b,int c,int d) { v.clear(); v.push_back(a); v.push_back(b); v.push_back(c); v.push_back(d); sort(v.begin(),v.end()); return v[0]; } int mn(int a,int b,int c) { v.clear(); v.push_back(a); v.push_back(b); v.push_back(c); sort(v.begin(),v.end()); return v[0]; } int main() { int t,X,slot,a,b,c,d; scanf("%d",&t); while(t--) { scanf("%d",&X); init(); slot = X/100; for(int i=9;i>=0;i--) { for(int j=0;j<slot;j++) { scanf("%d",&a); vb[i].push_back(a); } } dp[0][1]=30-vb[0][0]; dp[1][1]=60-vb[0][0]; for(int i=2;i<=slot;i++) { for(int j=0;j<=9;j++) { if(j>0 && j<9) { if(dp[j-1][i-1]==-1)a = INF; else a = dp[j-1][i-1]+60-vb[j-1][i-1]; if(dp[j][i-1]==-1)b = INF; else b = dp[j][i-1]+30-vb[j][i-1]; if(dp[j+1][i-1]==-1)c = INF; else c = dp[j+1][i-1]+20-vb[j+1][i-1]; if(dp[j][i]==-1)d = INF; else d = dp[j][i]; dp[j][i]=_min(a,b,c,d);//_min( dp[j-1][i-1]+60-vb[j-1][i-1], dp[j][i-1]+30-vb[j][i-1], dp[j+1][i-1]+20-vb[j+1][i-1] ); } else if(j==9) { if(dp[j-1][i-1]==-1)a = INF; else a = dp[j-1][i-1]+60-vb[j-1][i-1]; if(dp[j][i-1]==-1)b = INF; else b = dp[j][i-1]+30-vb[j][i-1]; if(dp[j][i]==-1)c = INF; else c = dp[j][i]; dp[j][i]=mn(a,b,c);//_min( dp[j-1][i-1]+60-vb[j-1][i-1], dp[j][i-1]+30-vb[j][i-1] ); } else if(j==0) { if(dp[j][i-1]==-1)a = INF; else a = dp[j][i-1]+30-vb[j][i-1]; if(dp[j+1][i-1]==-1)b = INF; else b = dp[j+1][i-1]+20-vb[j+1][i-1]; if(dp[j][i]==-1)c = INF; else c = dp[j][i]; dp[j][i]=mn(a,b,c);//_min( dp[j][i-1]+30-vb[j][i-1], dp[j+1][i-1]+20-vb[j+1][i-1] ); } } } cout<<dp[0][slot]<<"\n\n"; } return 0; } |