很久没有写过题了，最近越来越弱，被一道DP虐成洪特了……
由于格式原因直接挂链接：http://www.tyvj.cn/Problem_Show.asp?id=1013。
分析：乍看这题像是一个双条件背包，后来正准备上时发现由于本题还要考虑妹纸数最多，所以不能通过普通的背包来写。后来又准备先求出最多妹纸数，再求最短时间。可发现后面的问题并不便求解，于是傻眼了……苦思冥想半小时依然无解，只好向大神求助，结果发现居然如此简单……被虐了………………
方法：既然我们没必要把两个子问题分开写，我们就应该想想子问题之间的联系。结果发现：如果以现状搞到当前妹纸后会让总妹纸数增多，那么不管是否花时间更少，必须搞到这个妹纸；如果不会增多，那么再在此基础上考虑是否应当换成该妹纸使时间变少。这样一个优先级的关系使得我们可以用第一个状态转移第二个状态，这道题就很容易求解了。
设f[i][j][1]表示在RMB为I，RP为J的时候能搞到的最大妹纸数；f[i][j][2]表示该条件下所花的最少时间。则除了考虑f[i - rmb[k]][j-rp[k]][1]+1>f[i][j][1]时不论时间是否更优必须强制转状态以外，其余的就和0,1背包大同小异了。
View Code 1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int MAXN = 110; 9 const int MAXRMB = 110; 10 const int MAXR = 110; 11 12 int n, m, r, f[MAXRMB][MAXR][3], K; 13 int rmb[MAXN], rp[MAXN], time[MAXN], ans[MAXN]; 14 15 int main() { 16 scanf("%d", &n); 17 for (int i = 1; i <= n; i ++) 18 scanf("%d%d%d", &rmb[i], &rp[i], &time[i]); 19 scanf("%d%d", &m, &r); 20 21 for (int i = 1; i <= n; i ++) 22 for (int j = m; j >= rmb[i]; j --) 23 for (int k = r; k >= rp[i]; k --) { 24 if (f[ j - rmb[i] ][ k - rp[i] ][1] + 1 > f[j][k][1]) { 25 f[j][k][1] = f[ j - rmb[i] ][ k - rp[i] ][1] + 1; 26 f[j][k][2] = f[ j - rmb[i] ][ k - rp[i] ][2] + time[i]; 27 } 28 if (f[ j - rmb[i] ][ k - rp[i] ][1] + 1 == f[j][k][1]) 29 f[j][k][2] = min(f[j][k][2], f[ j - rmb[i] ][ k - rp[i] ][2] + time[i]); 30 } 31 32 printf("%d\n", f[m][r][2]); 33 return 0; 34 }
转载于:https://www.cnblogs.com/stickjitb/archive/2012/09/15/2687030.html
