[关闭]
@LinKArftc 2015-08-17T15:55:05.000000Z 字数 6497 阅读 2341

dp

动态规划

poj 1018 双关键字dp

题意

某公司要建立一套通信系统，该通信系统需要n种设备，而每种设备分别可以有m1、m2、m3、...、mn个厂家提供生产，而每个厂家生产的同种设备都会存在两个方面的差别：带宽bandwidths 和 价格prices。
现在每种设备都各需要1个，考虑到性价比问题，要求所挑选出来的n件设备，要使得B/P最大。
其中B为这n件设备的带宽的最小值，P为这n件设备的总价。

思路

我们定义状态 dp[i][j] 表示选择了前 i 个宽带其容量为 j 的最小费用。
很容易得到转移方程 ： dp[i][j] = min(dp[i][j], dp[i-1][k] + p);
注意选择 j 的时候的大小情况。

AC代码

  2. int dp[105][1005];//前 i 个device在带宽为 j 时的最小价格
  4. int main() {
  6.     int T;
  7.     scanf("%d", &T);
  8.     while (T --) {
  9.         memset(dp, 0x3f, sizeof(dp));
  10.         int n;
  11.         scanf("%d", &n);
  12.         for (int i = 1; i <= n; i ++) {
  13.             int mi;
  14.             scanf("%d", &mi);
  15.             for (int j = 1; j <= mi; j ++) {
  16.                 int b, p;
  17.                 scanf("%d %d", &b, &p);
  18.                 if (i == 1) dp[1][b] = min(dp[1][b], p);
  19.                 else {
  20.                     for (int k = 0; k < 1005; k ++) {
  21.                         if (dp[i-1][k] < inf) {
  22.                             if (k <= b) dp[i][k] = min(dp[i][k], dp[i-1][k] + p);
  23.                             else dp[i][b] = min(dp[i][b], dp[i-1][k] + p);
  24.                         }
  25.                     }
  26.                 }
  27.             }
  28.         }
  29.         double ans = 0.0;
  30.         for (int i = 0; i < 1005; i ++) {
  31.             if (dp[n][i] < inf) {
  32.                 ans = max(ans, (double)i / dp[n][i]);
  33.             }
  34.         }
  35.         printf("%.3f\n", ans);
  36.     }
  38.     return 0;
  39. }

POJ 1050 最大子矩阵和

题意

求最大子矩阵和 (n <= 100)

思路

将二维问题转化为一维，对于第 k 列，暴力求第 i 行到第 j 行的和，这样就转化为一维数组上求最大子段和。
复杂度 O(n^3)

AC代码

  2. const int maxn = 105;
  4. int arr[maxn][maxn];
  5. int sum[maxn];
  6. int n;
  8. int max_arr() {
  9.     int ret = 0;
  10.     int cur = 0;
  11.     for (int i = 1; i <= n; i ++) {
  12.         cur += sum[i];
  13.         if (cur > 0) ret = max(ret, cur);
  14.         else cur = 0;
  15.     }
  16.     return ret;
  17. }
  19. int main() {
  20.     while (~scanf("%d", &n)) {
  22.         for (int i = 1; i <= n; i ++) {
  23.             for (int j = 1;j <= n; j ++) {
  24.                 scanf("%d", &arr[i][j]);
  25.             }
  26.         }
  27.         int ans = 0;
  28.         for (int i = 1; i <= n; i ++) {
  29.             memset(sum, 0, sizeof(sum));
  30.             for (int j = i; j <= n; j ++) { //i -> j row
  31.                 for (int k = 1; k <= n; k ++) sum[k] += arr[j][k];
  32.                 int cur = max_arr();
  33.                 ans = max(ans, cur);
  34.             }
  35.         }
  36.         printf("%d\n", ans);
  37.     }
  39.     return 0;
  40. }

POJ 1088 滑雪

题意

经典的滑雪问题，连题号我都记住了= =，没事写来练练手

思路

记忆话搜索

AC代码

  2. const int maxn = 105;
  3. int n, m;
  4. int mp[maxn][maxn];
  5. int dp[maxn][maxn];
  6. int dx[] = { -1, 0, 1 , 0 };
  7. int dy[] = { 0, 1, 0, -1 };
  9. int search(int x, int y) {
  10.     if (dp[x][y]) return dp[x][y];
  11.     for (int i = 0; i < 4; i ++) {
  12.         int xx = x + dx[i];
  13.         int yy = y + dy[i];
  14.         if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && mp[xx][yy] > mp[x][y]) {
  15.             int cur = search(xx, yy);
  16.             dp[x][y] = max(dp[x][y], cur + 1);
  17.         }
  18.     }
  19.     return dp[x][y];
  20. }
  22. int main() {
  24.     while (~scanf("%d %d", &n, &m)) {
  25.         for (int i = 1; i <= n; i ++) {
  26.             for (int j = 1; j <= m; j ++) {
  27.                 scanf("%d", &mp[i][j]);
  28.             }
  29.         }
  30.         memset(dp, 0, sizeof(dp));
  31.         int ans = 0;
  32.         for (int i = 1; i <= n; i ++) {
  33.             for (int j = 1; j <= m; j ++) {
  34.                 int cur = search(i, j);
  35.                 ans = max(ans, cur);
  36.             }
  37.         }
  38.         printf("%d\n", ans + 1);
  39.     }
  41.     return 0;
  42. }

POJ 1189 概率dp

思路

写的第一道概率dp。
第i层有2*i+1种可能的位置（从第0个空位到最后一个空位总共i+1个和i个钉子位置），注意题目中下标从0开，用d[i][j]表示第i行在第j个位置掉落的概率的分子（分母是2^i）。

如果位置是空位，那么有3种情况：

  1. 从上一个同样的位置掉落下来
  2. 掉落到左边的钉子（如果有）并向右走
  3. 掉落到右边的钉子（如果有）并向左走。

如果位置是有钉子的，有2种情况：

  1. 这个位置有钉子，那么不可能以这个位置掉落
  2. 这个位置没有钉子，可以从上一个同样的位置掉落下来。

AC代码

  2. int mp[110][110];
  3. ll dp[110][210];
  4. int n, m;
  6. int main() {
  8.     scanf("%d %d", &n, &m);
  9.     char tmp;
  10.     for (int i = 1; i <= n; i ++) {
  11.         for (int j = 1; j <= i; j ++) {
  12.             scanf(" %c", &tmp);
  13.             if (tmp == '*') mp[i][j] = 1;
  14.             else mp[i][j] = 0;
  15.         }
  16.     }
  17.     if (mp[1][1] == 1) {
  18.         dp[1][1] = 1;
  19.         dp[1][2] = 0;
  20.         dp[1][3] = 1;
  21.     } else {
  22.         dp[1][1] = 0;
  23.         dp[1][2] = 2;
  24.         dp[1][3] = 0;
  25.     }
  26.     for (int i = 2; i <= n; i ++) {
  27.         dp[i][1] = mp[i][1] == 1 ? dp[i-1][1] : 0;
  28.         dp[i][2*i+1] = mp[i][i] == 1 ? dp[i-1][2*i-1] : 0;
  29.         for (int j = 2; j <= 2*i ; j ++) {
  30.             ll cur;
  31.             if (j % 2) {
  32.                 cur = dp[i-1][j-1] * 2;
  33.                 cur += mp[i][j/2] == 1 ? dp[i-1][j-2] : 0;
  34.                 cur += mp[i][j/2+1] == 1 ? dp[i-1][j] : 0;
  35.             } else {
  36.                 cur = mp[i][j/2] == 1 ? 0 : dp[i-1][j-1] * 2;
  37.             }
  38.             dp[i][j] = cur;
  39.         }
  40.     }
  41.     ll a = dp[n][2*m+1];
  42.     ll b = (ll)1 << n;
  43.     while ((a % 2 == 0) && (b % 2 == 0)) {
  44.         a /= 2;
  45.         b /= 2;
  46.     }
  47.     printf("%lld/%lld\n", a, b);
  49.     return 0;
  50. }

POJ 1322 概率dp

题意

一共有c种巧克力, 每种的个数都是一样多并且是足够多,现在从包里面拿出n次巧克力一次一个,当桌面上有2个相同的时候就吃掉这两个, 现在问你在拿出n次之后桌面上恰好有m个巧克力的概率.

思路

状态dp[i][j]: 第i次操作后, 桌面上出现j个巧克力的概率.因为每次吃两个，所以(i+j)为奇数是dp[i][j]=0。
状态转移：dp[i][j] = dp[i-1][j-1] * (c-j+1.0) / c + dp[i-1][j+1] * (j+1.0) / c;第i次只与第i-1次有关，所以空间可以压缩。
另外，由于C (C <= 100), N and M (N, M <= 1000000)，所以 O(C*N) 华丽丽的超时了，看网上的代码才知道因为精度是三位小数，所以当拿的次数大于1000时概率已经是趋于平衡。。= =||，万万没想到~~~

AC代码

  2. const int maxn = 105;
  3. int c, n, m;
  4. double dp[2][maxn];
  6. int main() {
  8.     while (~scanf("%d", &c) && c) {
  9.         scanf("%d %d", &n, &m);
  10.         if (m > c || m > n || ((m+n)&1)) {
  11.             printf("0.000\n");
  12.             continue;
  13.         }
  14.         memset(dp, 0, sizeof(dp));
  15.         dp[0][0] = 1;
  16.         if (n > 10000) n = 10000 + (n&1);
  17.         for (int i = 1; i <= n; i ++) {
  18.             for (int j = 0; j <= c; j ++) {
  19.                 if ((i+j)&1) continue;
  20.                 dp[i&1][j] = dp[(i-1)&1][j-1] * (c-j+1.0) / c + dp[(i-1)&1][j+1] * (j+1.0) / c;
  21.             }
  22.         }
  23.         printf("%.3f\n", dp[n&1][m]);
  24.     }
  26.     return 0;
  27. }

POJ 1609 双关键字dp

题意

n 个木板，每个木板有l,m两个属性，当a木板的l和m都大于等于b木板时，a可以放在b上面，问最多可以堆叠多少个木板

思路

num[i][j] 表示l=i，m=j的木板数目， dp[i][j] 表示l=i，m=j时最多可以堆叠的木板数目，则dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + num[i][j];

AC代码

  1. //把多余的头文件、注释和num数组去掉之后仍然有260K，不知道那些44K的大神是怎么写的= =
  2. const int maxn = 105;
  3. int n;
  4. int dp[maxn][maxn];
  5. int num[maxn][maxn];
  7. int main() {
  9.     while (~scanf("%d", &n) && n) {
  10.         int a, b;
  11.         memset(num, 0, sizeof(num));
  12.         memset(dp, 0, sizeof(dp));
  13.         for (int i = 1; i <= n; i ++) {
  14.             scanf("%d %d", &a, &b);
  15.             num[a][b] ++;
  16.         }
  17.         for (int i = 1; i <= 100; i ++) {
  18.             for (int j = 1; j <= 100; j ++) {
  19.                 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + num[i][j];
  20.             }
  21.         }
  22.         printf("%d\n", dp[100][100]);
  23.     }
  24.     printf("*\n");
  26.     return 0;
  27. }

POJ 1644 概率dp

题意

一个线性棋盘，一开始玩家在0位置，重点位置为m+1，每一轮抛硬币决定向右一步还是两步，概率各为0.5。棋盘每格上都会有一个说明+n，-n，L，或者0，分别意味着向右走n格，向左走n格，失去一轮机会，无任何说明。给出棋盘的大小，以及棋盘上每一格的说明，求在第t轮或者少于t轮便走到终点处的概率。概率恰好等于0.5，printf("Push. 0.5000\n");，大于0.5，printf("Bet for. %.4f\n", ans);，小于0.5，printf("Bet against. %.4f\n", ans);

思路

不难，dp[i][j]表示第i次走到j位置的概率

AC代码

  2. #define eps 1e-8
  3. const int inf = 0x3f3f3f3f;
  5. const int maxn = 60;
  6. int ins[maxn];
  7. double dp[maxn][maxn]; //第i次走到j位置的概率
  8. char str[5];
  9. int m, t;
  11. int main() {
  13.     int T;
  14.     scanf("%d", &T);
  15.     while (T --) {
  16.         scanf("%d %d", &m, &t);
  17.         ins[0] = 0;
  18.         ins[m + 1] = 0;
  19.         ins[m + 2] = -1;
  20.         for (int i = 1; i <= m; i ++) {
  21.             scanf("%s", str);
  22.             if (str[0] == 'L') ins[i] = inf;
  23.             else sscanf(str, "%d", &ins[i]);
  24.         }
  25.         memset(dp, 0, sizeof(dp));
  26.         dp[0][0] = 1.0;
  27.         for (int i = 0; i <= t; i ++) {
  28.             for (int j = 0; j <=m; j ++) {
  29.                 if (ins[j+1] == inf) dp[i+2][j+1] += dp[i][j] * 0.5;
  30.                 else dp[i+1][j+1+ins[j+1]] += dp[i][j] * 0.5;
  31.                 if (ins[j+2] == inf) dp[i+2][j+2] += dp[i][j] * 0.5;
  32.                 else dp[i+1][j+2+ins[j+2]] += dp[i][j] * 0.5;
  33.             }
  34.         }
  35.         double ans = 0.0;
  36.         for (int i = 0; i <= t; i ++) ans += dp[i][m+1];
  37.         if (fabs(ans - 0.5) < eps) printf("Push. 0.5000\n");
  38.         else if (ans > 0.5) printf("Bet for. %.4f\n", ans);
  39.         else printf("Bet against. %.4f\n", ans);
  40.     }
  41.     return 0;
  42. }

POJ 2385

题意

有两棵苹果树，标号分别为1,2。每分钟其中一棵树会掉下一个苹果，但不知道是哪棵，奶牛初始位置为1，从一个树跑到另一个树需要一分钟，但它最多只会跑W次。问你在T分钟内，奶牛最多能接到多少苹果。

思路

刚开始是想用三维 dp[i][j][k]表示奶牛第i分钟跑了j次在位置k最多能接到的苹果数，后来突然发现既然奶牛初始位置为1且只有两棵树，那j为奇数奶牛位置肯定为2，为偶数肯定为1，所以二维dp就可以了，dp[i][j]表示奶牛第i分钟跑了j次最多能接到的苹果数，所以j > 0时，用cur表示当前是哪颗苹果树掉苹果，则dp[i][j] = max(dp[i-1][j], dp[i-1][j-1[) + cnt; 如果j为奇数cnt = (cur == 2 ? 1 : 0);，否则cnt = (cur == 1 ? 1 : 0);

AC代码

  1. const int maxt = 1005;
  2. const int maxw = 35;
  4. int dp[maxt][maxw];
  5. int pos[maxt];
  7. int main() {
  9.     int t, w, cur;
  10.     scanf("%d %d", &t, &w);
  11.     memset(dp, 0, sizeof(dp));
  12.     for (int i = 1; i <= t; i ++) {
  13.         scanf("%d", &cur);
  14.         for (int j = 0; j <= w; j ++) {
  15.             if (j) dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]);
  16.             else dp[i][j] = dp[i-1][j];
  17.             if (j & 1) dp[i][j] += (cur == 2 ? 1 : 0);
  18.             else dp[i][j] += (cur == 1 ? 1 : 0);
  19.         }
  20.     }
  21.     int ans = -1;
  22.     for (int j = 1; j <= w; j ++) ans = max(ans, dp[t][j]);
  23.     printf("%d\n", ans);
  25.     return 0;
  26. }

POJ 2181

题意

n(1 <= n <= 150000) 个数组成的序列，sum初始值为0，求它的一个子序列，sum加上这个序列的每个奇数项，减去这个序列的每个偶数项，使得sum最大。

思路

dp[i][0]表示前i个数，总共选了偶数次得到的最大sum
dp[i][1]表示前i个数，总共选了奇数次得到的最大sum
所以：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] - num[i]);
dp[i][1] = max(dp[i-1][1], dp[i-1][0] + num[i]);

AC代码

  2. const int maxn = 150005;
  4. int dp[maxn][2];
  5. int num[maxn];
  7. int main() {
  9.     int n;
  10.     while (~scanf("%d", &n)) {
  11.         dp[0][0] = dp[0][1] = 0;
  12.         for (int i = 1; i <= n; i ++) scanf("%d", &num[i]);
  13.         for (int i = 1; i <= n; i ++) {
  14.             dp[i][0] = max(dp[i-1][0], dp[i-1][1] - num[i]);
  15.             dp[i][1] = max(dp[i-1][1], dp[i-1][0] + num[i]);
  16.         }
  17.         printf("%d\n", max(dp[n][0], dp[n][1]));
  18.     }
  20.     return 0;
  21. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注