正文 

当前位置： 首页 > 开发 > java教程

simplestringproblem（状压dp）(代码片段)

博客就叫Molex好了 博客就叫Molex好了     2022-11-03     218

关键词：

Simple String Problem

Recently, you have found your interest in string theory. Here is an interesting question about strings.

You are given a string S of length n consisting of the first k lowercase letters.

You are required to find two non-empty substrings (note that substrings must be consecutive) of S, such that the two substrings don‘t share any same letter. Here comes the question, what is the maximum product of the two substring lengths?


Input

The first line contains an integer T, meaning the number of the cases. 1 <= T <= 50.

For each test case, the first line consists of two integers n and k. (1 <= n <= 2000, 1 <= k <= 16).

The second line is a string of length n, consisting only the first k lowercase letters in the alphabet. For example, when k = 3, it consists of a, b, and c.

Output

For each test case, output the answer of the question.

Sample Input 
4
25 5
abcdeabcdeabcdeabcdeabcde
25 5
aaaaabbbbbcccccdddddeeeee
25 5
adcbadcbedbadedcbacbcadbc
3 2
aaa
Sample Output 
6
150
21
0
Hint

One possible option for the two chosen substrings for the first sample is "abc" and "de".

The two chosen substrings for the third sample are "ded" and "cbacbca".

In the fourth sample, we can‘t choose such two non-empty substrings, so the answer is 0.

 

题意:给你一个串和两个整数n和k，n表示串的长度，k表示串只有前k个小写字母，问你两个不含相同元素的连续子串的长度的最大乘积。

第一道状压dp。详见代码。

 

 

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string>
#include<math.h>
#include<algorithm>
#define MAX 2005
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;

int dp[(1<<16)+5];   //dp状态存储16个字母的存在情况，1存在0不存在
int max(int x,int y)
    return x>y?x:y;

int main()

    int t,n,k,i,j;
    char s[MAX];
    scanf("%d",&t);
    while(t--)
        scanf("%d%d",&n,&k);
        scanf(" %s",s);
        memset(dp,0,sizeof(dp));
        for(i=0;i<n;i++)    //O(n^2)i首j尾遍历字符串全部子串，在遍历的同时每加入新字符需要及时更新状态
            int tt=0;
            for(j=i;j<n;j++)
                tt|=1<<(s[j]-‘a‘);   //|=相当于加入s[j]字符
                dp[tt]=max(dp[tt],j-i+1);  //获取含某几种字符的子串最长长度
            
        
//上一步仅仅是获取了含某几种字符的最长长度，还需要考虑子问题：比如某状态有三种字符长度为4，而另一种状态仅有其中的两种字符长度就达到6，我们要使两个不含相同元素子串长度乘积最大，那么在不会有重叠字符的前提下，长度当然越大越好，所以还要更新子问题
        for(i=0;i<(1<<k);i++)   //枚举所有状态
            for(j=0;j<k;j++)   //枚举每种字符
                if(i&(1<<j))   //若i状态中有第j种字符
                    dp[i]=max(dp[i],dp[i^(1<<j)]);   //i状态去掉j字符的子问题（异或异为真，i^00000保持原状，仅^含1位变0）
                
            
        
        int maxx=0;
        for(i=0;i<(1<<k);i++)   //寻找最大值（1<<k-1为k个1，i^11111每位全部取反，即为寻找互补）
            maxx=max(maxx,dp[i]*dp[((1<<k)-1)^i]);
        
        printf("%d\n",maxx);
    
    return 0;

 

 

 

hoj2662经典状压dp//myfirst状压dp

题目链接：http://acm.hit.edu.cn/hoj/problem/view?id=26621.引言：用dp解决一个问题的时候很重要的一环就是状态的表示，一般来说，一个数组即可保存状态。但是有这样的一类题目，它们具有dp问题的特性，但状态中所包含的信息过多，... 查看详情

动态规划---状压dp2(代码片段)

今天模拟，状压dp又没写出来。。。还是不会啊，所以今天搞一下这个状压dp。这里有一道状压dp的板子题：CornFields就是一道很简单的状压裸题，但是要每次用一个二进制数表示一行的状态。附加一个关于位运算的总结：上题干... 查看详情

状压dp(代码片段)

这几天都在学习状压DP，总结一下，首先是状压DP的工具。类型符号规则例子按位与&同1为1，其余为09       00001001&5       000001011      &nb 查看详情

foreignnumber[状压dp]

...leInput　　123455SampleOutput　　24HINT　　Solution　　我们运用状压DP，令f[j][opt]表示当前余数为j，状态为opt的方案。　　状态记录的是：各个数字被用了几次。　　那么我们就可以状压了。先 查看详情

第一次接触状压dp(代码片段)

状压DP入门及理解*（另类的暴力）*    一般状态数不多的时候就会开数组，但是有的状态并不好表示，于是，状压DP就产生了。   状压DP应该是分两类的，一类是压缩状态，另一类是舍弃状态。  &... 查看详情

算法复习——状压dp

状压dp的核心在于，当我们不能通过表现单一的对象的状态来达到dp的最优子结构和无后效性原则时，我们可能保存多个元素的有关信息··这时候利用2进制的01来表示每个元素相关状态并将其压缩成2进制数就可以达到目的····... 查看详情

fzu2188状压dp

G-SimpleStringProblemTimeLimit:2000MS    MemoryLimit:32768KB    64bitIOFormat:%I64d&%I64uSubmitStatusPracticeFZU2218DescriptionRecently,youhavefoundyourinte 查看详情

dp-状压dp(代码片段)

...w.bilibili.com/video/BV1Z4411x7Kw?from=search&seid=13855865082722302053状压介绍：状态表示：  转移方程：i是当前节点，j是下一步要走的节点  子集枚举：核心代码：1。由当前枚举未知首先枚举状态，枚举S中包含的节点：枚... 查看详情

d.romanandnumbers(状压dp)(代码片段)

D.RomanandNumbers(状压dp)把nnn的每一位状压，问题等价于选择一个顺序走完这cntcntcnt个位使得(modm)=0\\pmodm=0(modm)=0答案。令dp[i][j]dp[i][j]dp[i][j]表示状态iii模mmm余jjj的答案。转移时需要注意最高位对应的数不能为000。初始化... 查看详情

poj2411mondriaan'sdream（状压dp）

【POJ2411】Mondriaan‘sDream（状压dp）TimeLimit:3000MS MemoryLimit:65536KTotalSubmissions:14107 Accepted:8152DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,aft 查看详情

状压dp初探·总结

...最优还是最优，无后还是无后，所以它比较好理解。 状压，顾名思义就是要将一些状压想办法压缩起来（可以压，也可以删）。其中这些状态都满足相似性和数量很多。这样才好压而且压得有意义。常见于一般的方格题，网 查看详情

各种dp分类整理

各种dp分类整理数位dp因为比较重要，单独写一篇见这篇状压dp某篇学术垃圾中指出，我们可以说，所有的dp都会有一个“状压”。只不过普通的dp压缩的比较浅显，而使用二进制的状压dp压的比较复杂，才叫它“状压dp”所以这里... 查看详情

b.littleponyandharmonychest(状压dp)(代码片段)

B.LittlePonyandHarmonyChest(状压dp)考虑bi≥59b_i\\ge59bi​≥59​时，bi=1b_i=1bi​=1更优。所以只需考虑bi≤59b_i\\le59bi​≤59。又因为bbb数组两两互质。即每个质因子只能被一个数使用。且≤59\\le59≤59的质因子只有161616个。考虑... 查看详情

poj2441状压dp

 ArrangetheBullsTimeLimit: 4000MS MemoryLimit: 65536KTotalSubmissions: 5289 Accepted: 2033DescriptionFarmerJohnson‘sBullsloveplayingbasketballverymuch.Butnoneofthemw 查看详情

poj2411状压dp经典

Mondriaan‘sDreamTimeLimit:3000MS MemoryLimit:65536KTotalSubmissions:16771 Accepted:9683DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,afterproducingthed 查看详情

zoj3471mostpowerful（状压dp）

Recently,researchersonMarshavediscoveredNpowerfulatoms.Allofthemaredifferent.Theseatomshavesomeproperties.Whentwooftheseatomscollide,oneofthemdisappearsandalotofpowerisproduced.Researchersknowthewayev 查看详情

jzoj3747(状压dp)

这题是一道状压DP,暂时还不是很懂.#include<cstdio>#include<cstring>#include<iostream>usingnamespacestd;constintLENM=1010,N=11,M=1e9+7;chars[N];intn,m,u,ind[200],f[LENM][1<<10],g[N],ans[N],gg[N 查看详情

状压dp

poj3254：裸#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>usingnamespacestd;#definerep(i,n)for(inti=1;i<=n;i++)#defineclr(x,c)memset(x,c,sizeof(x))const 查看详情