fzu2218 Simple String Problem
Accept: 2 Submit: 16
Time Limit: 2000 mSec Memory Limit : 32768 KB
Problem Description
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
Sample Output
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.
Source
第六届福建省大学生程序设计竞赛-重现赛(感谢承办方华侨大学)
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
#define inf 99999999
#define pi acos(-1.0)
#define maxn 2005
char s[maxn];
int b[140000],dp[140000];
int main()
{
int n,m,i,j,T,k,state,state1,num;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
scanf("%s",s+1);
memset(b,0,sizeof(b));
for(i=1;i<=n;i++){
state=0;
for(j=i;j<=n;j++){
state=state|( 1<<(s[j]-'a') ) ;
b[state]=max(b[state],j-i+1);
}
}
dp[0]=0;
for(state=1;state<=(1<<k)-1;state++){
dp[state]=b[state];
for(j=1;j<=k;j++){
if(state&(1<<(j-1)) ){
state1=state-(1<<(j-1));
dp[state]=max(dp[state],dp[state1]);
}
}
}
num=0;
for(state=1;state<=(1<<k)-1;state++){
state1=((1<<k)-1)^state;
num=max(num,dp[state]*dp[state1]);
}
printf("%d\n",num);
}
return 0;
}
最新文章
- 如何使用git命令添加文件和提交文件
- glassfish配置
- 浏览器-07 chromium 渲染1
- The Managed Metadata Service or Connection is currently not available 分类: Sharepoint 2015-07-09 13:28 5人阅读 评论(0) 收藏
- PMBOK学习笔记一
- APP,webapp 设计相关资料汇集区
- atitit。浏览器缓存机制 and 微信浏览器防止缓存的设计 attilax 总结
- ODI中删除数据的处理
- Windows7中搭建Android x86_64及armv8-a操作步骤
- hdu 5115 Dire Wolf
- 单源最短路径问题-Dijkstra算法
- jQuery操作input改变value属性值
- HashMap源码分析(二)
- 题解 P2763 【试题库问题】
- Thanks David&#39;s Share
- [URLSession sessionWithConfiguration:config delegate:self delegateQueue:[NSOperationQueue mainQueue]
- RTP 流媒体
- 使用DOM的方法获取所有li元素,然后使用jQuery()构造函数把它封装为jQuery对象
- 【Java并发编程】:并发新特性—Executor框架与线程池
- PHPCMS列表循环序列号自增标签代码