正文

uva10599lisdp,记忆化搜索

╰追憶似水年華ぃ╮  ╰追憶似水年華ぃ╮  2022-09-15  774

关键词：

题意：

　　给出r*c的网格，其中有些格子里面有垃圾，机器人从左上角移动到右下角，只能向右或向下移动。问机器人能清扫最多多少个含有垃圾的格子，有多少中方案，输出其中一种方案的格子编号。格子编号是从左上角第一个开始，一行一行的按自然数顺序编。起始行列是第一行第一列。所以例如一个格子的行列号为(ro,co),那么它的编号为bh=(ro-1)*column+co，其中column指这个格子有多少列。（我觉得原题里面有个错误，题目叙述倒数第二行应该是41(6,6)不是41(6,7)）。

题解：　　

　　显然，格子的编号都是递增的，每个含有垃圾的格子的编号也是递增的，要求能扫多少个有垃圾的格子，其实可以看成求这些垃圾格子编号的一个最长上升子序列(lis)，而且这和普通格子没关系。需要注意的就是求lis时格子编号大的一定不能在编号小的左边，可以在同一列上。因为机器人只能向下或向右走。所以判断的时候要判断一下两个格子的列大小，这个也可以转化为比较编号的大小：(bh-1)%colum，可以算一下这个式子正好算出格子的列号-1。当然，这里可以用其它办法判断。然后就是用dp[]数组记录最多清扫多少个格子，用save[]记录垃圾格子的编号，用num[]数组记录方案总数（就是看成普通lis求法），用patn[]数组记录当前状态是从哪里转移过来的，也就是记录路径。

详见代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn = 107;
 6 int Map[maxn][maxn];//存那个格子有垃圾
 7 int dp[maxn*maxn], num[maxn*maxn], path[maxn*maxn], save[maxn*maxn];//如上文所述
 8 int r, c, n;//格子行、列，有多少个垃圾格子
 9 
10 void print(int cur)//递归输出
11 {
12     if (path[cur] != -1)
13         print(path[cur]);
14     if (cur != n - 1 || Map[r][c])//因为从n-1开始调用，当右下角格子不是垃圾格子时不需要输出(cur!=n-1)，是垃圾格子时需要输出(Map[r][c])
15         printf(" %d", save[cur]);
16 }
17 
18 int main()
19 {
20     int cas = 1;
21     while (cin >> r >> c)
22     {
23         memset(Map, 0, sizeof(Map));
24         memset(save, 0, sizeof(save));
25         if (r == -1 && c == -1) break;
26         int a, b;
27         while (cin >> a >> b)
28         {
29             if (a == 0 && b == 0) break;
30             Map[a][b] = 1;
31         }
32         n = 0;
33         for (int i = 1; i <= r; i++)
34             for (int j = 1; j <= c; j++) {
35                 if (Map[i][j])
36                     save[n++] = (i - 1)*c + j;//为垃圾格子编号
37             }
38         if (!Map[r][c]) save[n++] = r*c;//因为最后要到达右下角，所以不管右下角是不是垃圾格子，都把它看成有，求"lis"过程好办点
39         for (int i = 0; i <= n; i++) {//dp过程，和求lis过程类似
40             dp[i] = 1; num[i] = 1; path[i] = -1;
41             for (int j = 0; j < i; j++) {
42                 if (((save[j] - 1) % c) <= ((save[i] - 1) % c)) {//比较列
43                     if (dp[i] == dp[j] + 1) {//此时相当于又多了一种到i状态(第i个数)的方案数，那么直接累加num[j]
44                         num[i] += num[j];
45                     }
46                     else if (dp[i] < dp[j] + 1) {//此时状态可更新
47                         dp[i] = dp[j] + 1;//更新状态
48                         num[i] = num[j];//改为新状态的方案
49                         path[i] = j;//由于有新的状态，所以记录到当前状态的上一个状态位置
50                     }
51                 }
52             }
53         }
54         if (!Map[r][c]) dp[n - 1]--;//当右下角那个不是垃圾格子时，能清理的垃圾格子数-1
55         printf("CASE#%d: %d %d", cas++, dp[n - 1], num[n - 1]);
56         print(n - 1);//输出路径
57         printf("
");
58     }
59     return 0;
60 }

UVa 10599 code_1

uva10123-notippingdp记忆化搜索

这题的题意是在双脚天平上有N块东西，依次从上面取走一些，最后使得这个天平保持平衡！解题：　　逆着来依次放入，如果可行那就可以，记得得有木板自身的重量。/*************************************************************************>... 查看详情

uva-11761-马尔可夫/记忆化搜索(代码片段)

...期望挑选次数。　　f[i]=1/(m1+m2)*(SUMf[i]+SUMf[i/x])+1,化简后记忆化搜索就好了，筛素数的时候要保存所有的素数所以不能根号优化。　　1#include<iostream& 查看详情

uva10891区间dp+记忆化搜索

https://vjudge.net/problem/UVA-10891给定一个序列x，A和B依次取数，规则是每次只能从头或者尾部取走若干个数，A和B采取的策略使得自己取出的数尽量和最大，A是先手，求最后A-B的得分。令f(i,j)表示对于[i,j]对应的序列，先手可以从中... 查看详情

uva10891gameofsum（区间dp（记忆化搜索））(代码片段)

题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1832题目大意：两个人在玩一个游戏：给你一行n个数字，每次只能从左端或者右端取一个或多个数字。每个人的分值就是他们各自取得... 查看详情

uva-1630folding(串折叠)(dp---记忆化搜索)

题意：给出一个由大写字母组成的长度为n(1<=n<=100)的串，“折叠”成一个尽量短的串。折叠可以嵌套。多解时可输出任意解。分析：1、dp[l][r]为l~r区间可折叠成的最短串的长度。2、ans[l][r]为l~r区间可折叠成的最短串。3、先... 查看详情

uva-10817headmaster'sheadache（状压dp+记忆化搜索）

题意：有M个已聘教师，N个候选老师，S个科目，已知每个老师的雇佣费和可教科目，已聘老师必须雇佣，要求每个科目至少两个老师教的情况下，最少的雇佣费用。分析：1、为让雇佣费尽可能少，雇佣的老师应教他所能教的所... 查看详情

wenbao与记忆化搜索(代码片段)

记忆化搜索：通俗地讲就是搜索的形式，dp的思想一些搜索难以完成，dp的动态转移方程又不好写的题，就会用到记忆化搜索，利用dp记录路径（相当于为dfs剪枝）用dfs进行模拟。。啦啦啦啦啦啦，，，，，，，，，好厉害！... 查看详情

uva10118freecandies

...的状态会有很多重复，搜索量仍然很大。这就是传说中的记忆化搜索。。。number数组表示每一列取了多少个数，ans每一列取得相应数字个数时的最优解。第九章前面的代码用了引用，在记忆化搜索里面很方便。这个题还要注意搜... 查看详情

uva103dp基础题，dag模型

１、UVA103嵌套n维空间　DAG模型记忆化搜索，或者　最长上升子序列。２、dp[i]=max(dp[j]+1),(第i个小于第j个)（１）//DAG模型记忆化搜索#include<bits/stdc++.h>usingnamespacestd;#pragmacomment(linker,"/STACK:102400000,102400000")#defineF(i,a,b)for( 查看详情

uva12589learningvector(代码片段)

大家都是用优雅的记忆化搜索做的，我最笨，懒得写记忆化，直接递推暴力转移了。这题的难点在贪心上。自己想出来了大概明天会写详细证明吧。。1#include<cstdio>2#include<iostream>3#include<cstring>4#include<algorithm>5usi... 查看详情

（记忆化+暴力）uva-12627erraticexpansion

题意：一个数列，一开始只有一个1，进行k次操作，每次操作都把数列中原本的数全都翻倍然后追加在数列的后面，形成了一个全新的数列，输出全新数列中l到r的和。分析：以上的题意是经过转化后的题意，变的非常简单... 查看详情

记忆化搜索

记忆化搜素是DP的一种形式记忆化搜素是DP的一种形式查看详情

搜索分析（dfsbfs递归记忆化搜索）

搜索分析（DFS、BFS、递归、记忆化搜索）1、线性查找在数组a[]={0,1,2,3,4,5,6,7,8,9,10}中查找1这个元素。（1）普通搜索方法，一个循环从0到10搜索，这里略。（2）递归（从中间向两边）1//递归一定要写成记忆化递归2#include&... 查看详情

uva10118freecandies

题解:记忆化搜索如何判断一个数是否已经出现？应用位运算即可....代码:#include<bits/stdc++.h>usingnamespacestd;#definepbpush_back#definempmake_pair#definesesecond#definefsfirst#defineLLlonglong#defineCLR(x)memset(x,0,sizeofx)#de 查看详情

uva10285longestrunonasnowboard

题解:记忆化搜索入门题代码:#include<bits/stdc++.h>usingnamespacestd;#definepbpush_back#definempmake_pair#definesesecond#definefsfirst#defineLLlonglong#defineCLR(x)memset(x,0,sizeofx)#defineMC(x,y)memcpy(x,y, 查看详情

记忆化搜索(代码片段)

记忆化搜索什么是记忆化搜索？百度百科：算法上依然是搜索的流程，但是搜索到的一些解用动态规划的那种思想和模式作一些保存。个人理解：就是每求到一个状态就保存下来，下次再遇到这个状态直接调用即可它有什么好处... 查看详情

[uva1637][dfs][记忆化]纸牌游戏doublepatience(代码片段)

写代码一定要注意!!!!!!我因为i+1写成了1+1改了一晚上!!!!!!(菜都写脸上了)题目:DoublePatience是一种单人游戏，使用标准的36张牌组。这些牌在洗牌后放在一张桌子上，叠成9叠，每叠4张，面朝上。牌放下后，玩家转身。每一次，他可... 查看详情

uva1629cakeslicing

题解:记忆化搜索如何判断每个区域只有一个点？转化为区间和，只要区间和为1即可代码:#include<bits/stdc++.h>usingnamespacestd;#definepbpush_back#definempmake_pair#definesesecond#definefsfirst#defineLLlonglong#defineCLR(x)memset(x,0,sizeof 查看详情