dp专题题目记录

青旅半醒 2023-08-17 16:26 193阅读 0赞

1.数的划分    2星

[https://ac.nowcoder.com/acm/problem/16695][https_ac.nowcoder.com_acm_problem_16695]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 #define ll long long
     4 #define eps 1e-6
     5 int ans=0;
     6 int n, k;
     7 void dfs(int id, int sum, int val)
     8 {
     9     /*if(id == k-1 && sum + val <= n){  //存在最后一个数字n-sum>=val   集合里面的数字是递增的 
    10         ans++;
    11         return;
    12     }
    13     for(int i = val; i <= n; i++){
    14         if(sum + i >n)
    15             break;
    16         dfs( id + 1, sum + i, i);
    17     }*/ 
    18    if(id==k&&sum==n)
    19     {
    20         ans++;
    21         return;
    22      }
    23       
    24     if(id>=k||sum>n)
    25     return;
    26     
    27     for(int i = val; i <= n; i++){
    28         if(sum+i>n)
    29         break;
    30         dfs(id+1,sum+i,i);
    31     }
    32 }
    33  
    34 int main()
    35 {
    36     while(scanf("%d %d", &n, &k) != EOF){
    37         ans = 0;
    38         dfs(0, 0, 1);
    39         printf("%d\n", ans);
    40     }
    41     return 0;
    42 }

[https://www.jianshu.com/p/0f402c15903c][https_www.jianshu.com_p_0f402c15903c]

[https://blog.csdn.net/wjc1761659069/article/details/87298513][https_blog.csdn.net_wjc1761659069_article_details_87298513]

2.单词接龙   3星

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 
     4 struct node{
     5     char s[22];
     6     int len;
     7     int v;//被选的次数 
     8 }c[22];
     9 int n,maxn;
    10 
    11 void dfs(int x,int len){
         //当前单词序号   目前龙的长度 
    12     for(int i=1;i<=n;i++){   //可以选n种单词 
    13         if(c[i].v<2)//被选的次数小于2 
    14         {
    15             for(int j=0;j<c[x].len;j++){   //判断前一个单词是否和当前所选的单词有相等的地方 
    16                 if(c[x].s[j]==c[i].s[0]){   
    17                 int k=1,t=1,l;
    18                 for(l=j+1;l<c[x].len&&k<c[i].len;++k,++l){
    19                     if(c[x].s[l]!=c[i].s[k])
    20                     {
    21                         t=0;   break;
    22                     }
    23                 }
    24                 if(l!=c[x].len)  //说明单词i被单词x包含 
    25                 t=0;
    26                 if(t)  //说明单词x与单词i相连且不被包含 
    27                 {
    28                     c[i].v++;
    29                     dfs(i,len+c[i].len-k);  
    30                     c[i].v--;
    31                 }                
    32                 }
    33             }
    34         }
    35     }
    36     maxn=max(maxn,len);
    37 }
    38 
    39 int main(){
    40     cin>>n;//单词数
    41     for(int i=1;i<=n;i++){
    42     cin>>c[i].s;//第一个单词内容 
    43     c[i].len=strlen(c[i].s);//第一个单词长度 
    44     }
    45     cin>>c[0].s;//成语接龙首字母    
    46     c[0].len=strlen(c[0].s);
    47     
    48     dfs(0,c[0].len);
    49     cout<<maxn<<endl;
    50 }

使用dfs的情况：搜索值最大的方案
    方案由几个x组成，x又有n种方案，对x进行dfs
    void dfs(int x)
    {
    for(int i=0;i<n;i++)
    ...
    }

转载于:https://www.cnblogs.com/Aiahtwo/p/11391017.html

[https_ac.nowcoder.com_acm_problem_16695]: https://ac.nowcoder.com/acm/problem/16695
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230810/daa35210d24a4cebbcc0e5ec8166e960.png
[https_www.jianshu.com_p_0f402c15903c]: https://www.jianshu.com/p/0f402c15903c
[https_blog.csdn.net_wjc1761659069_article_details_87298513]: https://blog.csdn.net/wjc1761659069/article/details/87298513