• 记忆化搜索 day48

    今天听完派队的教学

    感觉又可以水几道紫题了

    好耶✌

    不过想起ygg提到的记忆化搜索

    自己其实也是没有搞懂的

    还是去做了几道题吧

     P2476 [SCOI2008]着色方案

    紫题喵

    最开始想的是一个这样的状态

    f[i][j] 表示的是 第i块板子 前一块用的是编号为j的颜色

    其实我们仔细想想就可以想出来 这个状态表示是有会漏情况的 比如1为头的时候

    我们再搜3的时候 后面有的情况是有的 但是我们就直接返回了

    后来被他们讲到 这就是有后效性 意会一下

    一个可做的做法 

    我们观察道c1 的数据范围奇小无比 并且抽象一下可以用ci的大小来划分成5种集合 

    非常牛逼！

    这样我们就可以写出状态转移方程：

    f[c1​][c2​][c3​][c4​][c5​][last]=

    [c_1 - (last == 2)] * f[c_1 - 1][c_2][c_3[c_4][c_5][1] +[c1​−(last==2)]∗f[c1​−1][c2​][c3​[c4​][c5​][1]+

    [c_2 - (last == 3)] * f[c_1 + 1][c_2 - 1][c_3][c_4][c_5][2] +[c2​−(last==3)]∗f[c1​+1][c2​−1][c3​][c4​][c5​][2]+

    [c_3 - (last == 4)] * f[c_1][c_2 + 1][c_3 - 1][c_4][c_5][3] +[c3​−(last==4)]∗f[c1​][c2​+1][c3​−1][c4​][c5​][3]+

    [c_4 - (last == 5)] * f[c_1][c_2][c_3 + 1][c_4 - 1][c_5][4] +[c4​−(last==5)]∗f[c1​][c2​][c3​+1][c4​−1][c5​][4]+

    c_5 * f[c_1][c_2][c_3][c_4 + 1][c_5 - 1][5]c5​∗f[c1​][c2​][c3​][c4​+1][c5​−1][5]

    这样子确实是不重不漏的

    我们可以这样子理解记忆化搜索：

    我们就是在爆搜 但是加了一个不重不漏的集合 来优化

    下面的dfs 也是很符合爆搜

    就像是在枚举这一位到底填啥 让后根据填的啥规定系数

    1. #include 
    2. using namespace std;
    3. const int N = 20;
    4. const int M = 1<<16;
    5. const int mod = 1e9+7;
    6. #define int long long
    7. #define LL long long
    8. #define endl '\n'
    9. #define Endl '\n'
    10. #define _ 0
    11. #define inf 0x3f3f3f3f3f3f3f3f
    12. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    13. int n,f[16][16][16][16][16][6],t[6];
    14. int dfs(int a,int b,int c,int d,int e,int last){
    15.     int &v=f[a][b][c][d][e][last];
    16.     if(v)return v;
    17.     if(!a&&!b&&!c&&!d&&!e)return 1;
    18.     int cnt=0;
    19.     if(a) cnt=(cnt+(a-(last==2))*dfs(a-1,b,c,d,e,1))%mod;
    20.     if(b) cnt=(cnt+(b-(last==3))*dfs(a+1,b-1,c,d,e,2))%mod;
    21.     if(c) cnt=(cnt+(c-(last==4))*dfs(a,b+1,c-1,d,e,3))%mod;
    22.     if(d) cnt=(cnt+(d-(last==5))*dfs(a,b,c+1,d-1,e,4))%mod;
    23.     if(e) cnt=(cnt+e*dfs(a,b,c,d+1,e-1,5))%mod;
    24.     v=cnt%mod;
    25.     return v;
    26. }
    27. signed main(){
    28.     fast
    29.     cin>>n;
    30.     for(int i=1;i<=n;i++){
    31.         int x;cin>>x;
    32.         t[x]++;
    33.     }
    34.     cout<<dfs(t[1],t[2],t[3],t[4],t[5],0)<
    35.     return ~~(0^_^0);
    36. }

    P4850 [IOI2009] 葡萄干 raisins

    我们首先来考虑状态如何表示

    数据范围只有50 并且切的刀数也是固定的

    状态表示就4维就好了 f[x1][x2][y1][y2]表示矩阵类的min 吧

    这里和动态规划差不多 属性不一样 dfs 过程也不一样 cnt+= min枚举取min

    那我们在考虑爆搜咋写 其实就是枚举横着切 在哪切 竖着在哪切 最后加上自己当前大小的sum

    1. #include 
    2. using namespace std;
    3. const int N = 55;
    4. const int M = 1<<16;
    5. const int mod = 1e9+7;
    6. #define int long long
    7. #define LL long long
    8. #define endl '\n'
    9. #define Endl '\n'
    10. #define _ 0
    11. #define inf 0x3f3f3f3f3f3f3f3f
    12. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    13. int n,m,f[N][N][N][N],sum[N][N];
    14. int dfs(int x1,int x2,int y1,int y2){
    15.     if(f[x1][x2][y1][y2])return f[x1][x2][y1][y2];
    16.     if(x1==x2&&y1==y2)return 0;
    17.     f[x1][x2][y1][y2]=inf;
    18.     int cut=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
    19.     for(int i=x1;i
    20.         f[x1][x2][y1][y2]=min(f[x1][x2][y1][y2],dfs(x1,i,y1,y2)+dfs(i+1,x2,y1,y2));
    21.     }
    22.     for(int i=y1;i
    23.         f[x1][x2][y1][y2]=min(f[x1][x2][y1][y2],dfs(x1,x2,y1,i)+dfs(x1,x2,i+1,y2));
    24.     }
    25.     f[x1][x2][y1][y2]+=cut;
    26.     return f[x1][x2][y1][y2];
    27. }
    28. signed main(){
    29.     fast
    30.     cin>>n>>m;
    31.     for(int i=1;i<=n;i++){
    32.         for(int j=1;j<=m;j++){
    33.             int x;cin>>x;
    34.             sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+x;
    35.         }
    36.     }
    37.     cout<<dfs(1,n,1,m)<
    38.     return ~~(0^_^0);
    39. }

    P3609 [USACO17JAN]Hoof, Paper, Scissor G

    哦 这道题不是记忆化搜索

    但是他tag写的记忆化搜索

    并且题解也全是记忆化搜索

    但是我一眼就是dp啊

    就很普通的一个dp

    f[i][j][k] 表示我们现在是第i个手势 我们变化了j次 并且上次手势是k

    时间复杂度就是O（1e5*20*3) 完全可以通过这道题

    1. #include 
    2. using namespace std;
    3. const int N = 1e5+10;
    4. const int M = 1<<16;
    5. const int mod = 1e9+7;
    6. #define int long long
    7. #define LL long long
    8. #define endl '\n'
    9. #define Endl '\n'
    10. #define _ 0
    11. #define inf 0x3f3f3f3f3f3f3f3f
    12. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    13. int a[N],f[N][22][3];
    14. signed main(){
    15.     fast
    16.     int n,m;cin>>n>>m;
    17.     for(int i=1;i<=n;i++){
    18.         char c;cin>>c;
    19.         if(c=='H')a[i]=0;
    20.         else if(c=='S')a[i]=1;
    21.         else a[i]=2;
    22.     }
    23.     for(int i=1;i<=n;i++){
    24.         for(int j=0;j<=m;j++){
    25.             for(int k=0;k<3;k++){
    26.                 int k1,k2;
    27.                 if(k==0) k1=1,k2=2;
    28.                 else if(k==1) k1=0,k2=2;
    29.                 else k1=0,k2=1;
    30.                 if(k-a[i]==-1||(k==2&&a[i]==0))f[i][j][k]=max(max(f[i-1][j][k],f[i-1][j-1][k1]),f[i-1][j-1][k2])+1;
    31.                 else f[i][j][k]=max(max(f[i-1][j][k],f[i-1][j-1][k1]),f[i-1][j-1][k2]);
    32.             }
    33.         }
    34.     }
    35.     cout<<max(f[n][m][0],max(f[n][m][1],f[n][m][2]))<
    36.     return ~~(0^_^0);
    37. }

    P1278 单词游戏

    我们来想这道题的状态表示是啥

    其实这里借鉴了状态压缩二进制的思想

    就是二进制拼凑

    f[i][j]表示在j状态下的当前数为i的max （我们还得知道当前数是谁是吧

    爆搜咋做 ？

    就是枚举每一个后面的可以接的单词 over 

    1. #include 
    2. using namespace std;
    3. const int N = 1e5+10;
    4. const int M = 1<<16;
    5. //const int mod = 1e9+7;
    6. #define int long long
    7. #define LL long long
    8. #define endl '\n'
    9. #define Endl '\n'
    10. #define _ 0
    11. #define inf 0x3f3f3f3f3f3f3f3f
    12. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    13. int f[18][M],n;
    14. string s[N];
    15. vector<int>v[300];//首字母是是啥
    16. int dfs(int x,int y){
    17.     if(f[x][y])return f[x][y];
    18.     int ans=0;
    19.     for(auto i:v[s[x].back()]){
    20.         if((y>>(i-1)&1)==0)ans=max(ans,dfs(i,y|(1<<(i-1))));
    21.     }
    22.     return f[x][y]=ans+s[x].size();
    23. }
    24. signed main(){
    25.     fast
    26.     cin>>n;
    27.     for(int i=1;i<=n;i++){
    28.         cin>>s[i];
    29.         v[s[i][0]].push_back(i);
    30.     }
    31.     int ans=-2e9;
    32.     for(int i=1;i<=n;i++)ans=max(ans,dfs(i,1<<(i-1)));
    33.     cout<
    34.     return ~~(0^_^0);
    35. }

    691. 立方体IV

    我这道题第一遍不是记忆化搜索做的

    就是很简单的找旁边有没有他爹

    有的话标记为1

    然后跑一遍连续的1 就可以了 O（1e6*100）

    然后题解介绍了一种记忆化搜索的方法

    我们首先想状态 

    其实直接就是f[i] i这个点可以连多长了

    我们爆搜 每一个点 要是旁边有他爹 就延续下去

    这个时间复杂度是一样的

    1. #include 
    2. using namespace std;
    3. const int N = 1e3+10;
    4. const int M = 1e6+10;
    5. const int mod = 1e9+7;
    6. #define int long long
    7. #define LL long long
    8. #define endl '\n'
    9. #define Endl '\n'
    10. #define _ 0
    11. #define inf 0x3f3f3f3f3f3f3f3f
    12. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    13. int w[N][N];
    14. vectorint,int>>v[M];
    15. signed main(){
    16.     fast
    17.     int t;cin>>t;
    18.     int tt=0;
    19.     while(t--){
    20.         tt++;
    21.         int n;cin>>n;
    22.         memset(w,0,sizeof w);
    23.         memset(v,0,sizeof v);
    24.         for(int i=1;i<=n;i++){
    25.             for(int j=1;j<=n;j++){
    26.                 cin>>w[i][j];
    27.                 v[w[i][j]].emplace_back(i,j);
    28.             }
    29.         }
    30.         if(n==1){
    31.             printf("Case #%d: 1 1\n",tt);
    32.             continue;
    33.         }
    34.         int a[M]={0};
    35.         for(int i=1;i<=n*n;i++){
    36.             auto x=v[i].back().first,y=v[i].back().second;
    37.             if(x-1>=1&&w[x-1][y]==i+1){a[i]=1;continue;}
    38.             if(x+1<=n&&w[x+1][y]==i+1){a[i]=1;continue;}
    39.             if(y-1>=1&&w[x][y-1]==i+1){a[i]=1;continue;}
    40.             if(y+1<=n&&w[x][y+1]==i+1){a[i]=1;}
    41.         }
    42.         int ans=0,cnt=0,num;
    43.         for(int i=1;i<=n*n;i++){
    44.             if(a[i])cnt++;
    45.             else cnt=0;
    46.             if(cnt>ans){
    47.                 num=i;
    48.                 ans=cnt;
    49.             }
    50.         }
    51.         while(a[num])num--;
    52.         printf("Case #%d: %d %d\n",tt,num+1,ans+1);
    53.     }
    54.     return ~~(0^_^0);
    55. }

    记忆化搜索版

    1. #include 
    2. using namespace std;
    3. const int N = 1e3+10;
    4. const int M = 1e6+10;
    5. const int mod = 1e9+7;
    6. #define int long long
    7. #define LL long long
    8. #define endl '\n'
    9. #define Endl '\n'
    10. #define _ 0
    11. #define inf 0x3f3f3f3f3f3f3f3f
    12. #define fast ios::sync_with_stdio(false);cin.tie(nullptr);
    13. int w[N][N],n,f[M];
    14. int dfs(int x,int y,int d){
    15.     if(f[d])return f[d];
    16.     int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
    17.     int ans=0;
    18.     for(int i=0;i<4;i++){
    19.         int x1=x+dx[i],y1=y+dy[i];
    20.         if(w[x1][y1]==d+1){
    21.             ans=dfs(x1,y1,d+1);
    22.             break;
    23.         }
    24.     }
    25.     return f[d]=ans+1;
    26. }
    27. signed main(){
    28.     fast
    29.     int t;cin>>t;
    30.     for(int C=1;t;t--,C++){
    31.         cin>>n;
    32.         memset(w,0,sizeof w);
    33.         memset(f,0,sizeof f);
    34.         for(int i=1;i<=n;i++){
    35.             for(int j=1;j<=n;j++){
    36.                 cin>>w[i][j];
    37.             }
    38.         }
    39.         int ans=0,id=0;
    40.         for(int i=1;i<=n;i++){
    41.             for(int j=1;j<=n;j++){
    42.                 int res=dfs(i,j,w[i][j]);
    43.                 if(res>ans){
    44.                     ans=res,id=w[i][j];
    45.                 }else if(res==ans&&id>w[i][j]){
    46.                     id=w[i][j];
    47.                 }
    48.             }
    49.         }
    50.         printf("Case #%d: %d %d\n",C,id,ans);
    51.     }
    52.     return ~~(0^_^0);
    53. }

  • 相关阅读:
    工具学习--easyexcel-3.x 使用--写入基本使用，自定义转换--动态表头以及宽设置-
    vue3_setup基础_渲染函数（ref,reactive）
    [Qt]信号和槽机制
    Java学习笔记：高级数据过滤
    oracle查询相同条件重复值只取第1条
    每日一题AC
    vue3项目中引用tailwindcss与heroicons
    Mac系统下TestCafe初体验
    数据结构与算法编程题2
    Linux中ROS话题通信中发布者基本操作（C++实现）
  • 原文地址：https://blog.csdn.net/qq_23852555/article/details/126145785