CODE[VS] 1040 단어 개수 집계
3399 단어 CODE[VS]
길이가 200을 넘지 않는 소문자 영문 자모로 구성된 자모열을 제시한다.이 알파벳을 k부로 나누기를 요구합니다. (단어는 6개를 넘지 않는 사전에서 나온다. 최대 개수를 출력해야 합니다.
설명 입력 Input Description
첫 번째 행위는 하나의 정수(0각 그룹의 첫 줄에 두 개의 정수(p,k)p가 문자열의 줄 수를 나타낸다.k는 k부분으로 나뉘는 것을 나타낸다.다음 p 줄은 줄마다 20자입니다.그 다음에 사전의 단어 개수를 나타내는 정수 s가 있다.(1<=s<=6) 다음 s줄은 줄마다 단어가 하나씩 있습니다.
출력 설명 Output Description
줄마다 정수가 하나씩 있고 각 그룹의 테스트 데이터에 대응하는 상응하는 결과이다.
샘플 Sample Input 입력
1 1 3 thisisabookyouareaoh 4 is a ok sab
샘플 출력 Sample Output
7
데이터 범위 및 프롬프트 Data Size & Hint
this/isabookyoua/reaoh
이것은 구분형 동태 기획의 제목이다.제목의 뜻은 가장 긴 200개의 문자열을 구분하여 k부분으로 나누고 p개의 단어를 제시하는 것이다. 이 k개의 부분에서 단어가 가장 많이 나오도록 요구하지만 한 가지 요구는 예를 들어this이다. 만약에 그가this라는 단어를 포함한다면this가 있으면 t나th나thi가 될 수 없고 is나s나his, 즉 자열의 첫 번째 자모가 여러 번 나올 수 없다.
그러면 이 문제에 대해 구분을 한다면 몇 번 전에 우리가 구분형 DP에 대한 이해를 통해 일반적인 형식은 i에서 j로 구분하면 t로 구분된 j-1부에 t+1에서 i로 조건을 만족시키는 개수를 더하는 것이다. 이 중에서 가장 좋은 해석이다.
이 문제에 대해 우리는 i에서 j까지의 단어의 개수를 저장할 수 있는 그룹을 새로 만들어야 한다. 우리는 뒤에서 앞으로 옮겨다니기를 선택한다. 왜냐하면 문제에서 말하는 자열의 첫 번째 자모에 여러 번의 문제가 발생하지 않도록 할 수 있기 때문이다.이것은 비교적 실현하기 쉽다. STL에서string을 이용한다.find()는 비교적 쉽게 얻을 수 있다.
동적 전환 방정식:
check[i][j]=check[i+1][j]i에서 j까지 하위 문자열
check[i][j]=check[i+1][j]i에서 j까지 하위 문자열 없음
dp[i][j]=max(dp[i][j], dp[t][j-1]+check[t+1][i])j는 구분된 개수, j-1<=t 코드 참조:
/*************************************************************************
> File Name: .cpp
> Author: Zhanghaoran0
> Mail: [email protected]
> Created Time: 2015 07 25 09 00 12
************************************************************************/
#include
#include
#include
#include
using namespace std;
int n, p, k, s;
string str;
string word[7];
int check[201][201];
int dp[201][201];
void DP();
void work(){
bool flag;
for(int j = str.size() - 1; j >= 0; j --){
for(int i = j; i >= 0; i --){
for(int l = 1; l <= s; l ++){
flag = false;
if(str.find(word[l], i) == i && word[l].size() <= j - i + 1){ //str.find(s, i) str i ， s， ， s str 。
flag = true;
break;
}
}
if(flag){
check[i][j] = check[i + 1][j] + 1;
}
else
check[i][j] = check[i + 1][j];
}
}
DP();
}
void DP(){
for(int i = 0; i < str.size(); i ++){
dp[i][1] = check[0][i];
}
for(int j = 2; j <= k; j ++){
for(int i = j - 1; i < str.size(); i ++){
for(int t = i - 1; t >= j - 1; t --){
dp[i][j] = max(dp[i][j], dp[t][j - 1] + check[t + 1][i]);
}
}
}
}
int main(void){
freopen("in.txt", "r", stdin);
string temp;
memset(check, 0, sizeof(check));
memset(dp, 0, sizeof(dp));
cin >> n;
while(n --){
cin >> p >> k;
str = "";
while(p --){
cin >> temp;
str += temp;
}
cin >> s;
for(int i = 1; i <= s; i ++){
cin >> word[i];
}
work();
cout << dp[str.size() - 1][k] << endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
CODE[VS] 1040 단어 개수 집계길이가 200을 넘지 않는 소문자 영문 자모로 구성된 자모열을 제시한다.이 알파벳을 k부로 나누기를 요구합니다. 설명 입력 Input Description 첫 번째 행위는 하나의 정수(0각 그룹의 첫 줄에 두 개의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
