hdu 5903 Square Distance(dp)

Problem Description

A string is called a square string if it can be obtained by concatenating two copies of the same string. For example, "abab", "aa" are square strings, while "aaa", "abba" are not.

Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

Peter has a string s=s1s2...sn of even length. He wants to find a lexicographically smallest square string t=t1t2...tn that the hamming distance between s and t is exact m. In addition, both s and t should consist only of lowercase English letters.

Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first contains two integers n and m (1≤n≤1000,0≤m≤n,n is even) -- the length of the string and the hamming distance. The second line contains the string s.

Output

For each test case, if there is no such square string, output "Impossible" (without the quotes). Otherwise, output the lexicographically smallest square string.

题意:给你一个长度为n的s串,一个数m,现在让你构造一个长度也为n的t串,使这个串是由两个相同的串拼起来的,并且和s串对应的位不同的数量为m。

而且使t的字典序尽量小。

一开始会想到贪心,但是显然单纯的贪心无法得到正确结果。于是要利用到dp

dp[i][count]表示取到i位有count个位置不一样是否成立。dp[i][count]+=dp[i+1][count-gg](gg表示要变的位置数)

这题要分几种情况

(1)s[i]==s[i+n/2],这个时候要么不变位置要么就变2次。

(2)s[i]!=s[i+n/2],这是要么变2次要么变1次。

由于要求字典序要最小,所以尽量要从首位开始变。于是递推要从n/2开始,这样才能保证前面的操作能使后续操纵成立。

#include <iostream>
#include <cstring>
using namespace std;
char s[1010];
int dp[1010][1010];
int main()
{
    int t;
    cin >> t;
    while(t--) {
        int n , m;
        cin >> n >> m;
        cin >> (s + 1);
        int count = m;
        memset(dp , 0 , sizeof(dp));
        dp[n / 2 + 1][0] = 1;
        for(int i = n / 2 ; i >= 1 ; i--) {
            if(s[i] == s[i + n / 2]) {
                for(int j = 0 ; j <= m ; j++) {
                    dp[i][j] += dp[i + 1][j];
                }
                for(int j = 2 ; j <= m ; j++) {
                    dp[i][j] += dp[i + 1][j - 2];
                }
            }
            else {
                for(int j = 1 ; j <= m ; j++) {
                    dp[i][j] += dp[i + 1][j - 1];
                }
                for(int j = 2 ; j <= m ; j++) {
                    dp[i][j] += dp[i + 1][j - 2];
                }
            }
        }
        if(!dp[1][m]) {
            cout << "Impossible" << endl;
            continue;
        }
        for(int i = 1 ; i <= n / 2 ; i++) {
            for(int j = 0 ; j < 26 ; j++) {
                int temp = (s[i] != j + ‘a‘) + (s[i + n / 2] != j + ‘a‘);
                if(dp[i + 1][m - temp]) {
                    s[i] = s[i + n / 2] = j + ‘a‘;
                    m -= temp;
                    break;
                }
            }
        }
        cout << s + 1 << endl;
    }
    return 0;
}
时间: 11-11

hdu 5903 Square Distance(dp)的相关文章

HDU 5903 Square Distance

$dp$预处理,贪心. 因为$t$串前半部分和后半部分是一样的,所以只要构造前一半就可以了. 因为要求字典序最小,所以肯定是从第一位开始贪心选择,$a,b,c,d,...z$,一个一个尝试过去,如果发现某字符可行,那么该位就选择该字符. 第$i$位选择字符$X$可行的条件: 记这一位选择字符$X$的情况下,对$dis$的贡献为$Q$,$1$至$i-1$位对$dis$贡献和为$F$: 如果第$i+1$位至第$\frac{n}{2}$位,对$dis$的贡献可以凑出$m-Q-F$,那么该位选择$X$可

hdu 1398 Square Coins(母函数|完全背包)

http://acm.hdu.edu.cn/showproblem.php?pid=1398 题意:有价值为1^2,2^2....7^2的硬币共17种,每种硬币都有无限个.问用这些硬币能够组成价值为n的钱数共有几种方案数. 母函数: #include <stdio.h> #include <iostream> #include <map> #include <set> #include <stack> #include <vector>

HDU 4960 (水dp)

Another OCD Patient Problem Description Xiaoji is an OCD (obsessive-compulsive disorder) patient. This morning, his children played with plasticene. They broke the plasticene into N pieces, and put them in a line. Each piece has a volume Vi. Since Xi

HDU 1087 &amp;&amp; POJ 2533(DP,最长上升子序列).

~~~~ 两道题的意思差不多,HDU上是求最长上升子序列的和,而POJ上就的是其长度. 貌似还有用二分写的nlogn的算法,不过这俩题n^2就可以过嘛.. ~~~~ 题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1087 http://poj.org/problem?id=2533 ~~~~ HDU1087: #include<cstdio> #include<cstring> #include<algorithm> #

hdu 2296 aC自动机+dp(得到价值最大的字符串)

Ring Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3180    Accepted Submission(s): 1033 Problem Description For the hope of a forever love, Steven is planning to send a ring to Jane with a rom

hdu 2457 AC自动机+dp

DNA repair Time Limit: 5000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2004    Accepted Submission(s): 1085 Problem Description Biologists finally invent techniques of repairing DNA that contains segments c

[ACM] hdu 3555 Bomb (数位DP,统计1-N中含有“49”的总数)

Bomb Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) Total Submission(s): 7187 Accepted Submission(s): 2512 Problem Description The counter-terrorists found a time bomb in the dust. But this time the terrorists impro

HDU 4833 Best Financing DP

Best Financing Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 120    Accepted Submission(s): 24 Problem Description 小 A想通过合理投资银行理财产品达到收益最大化.已知小A在未来一段时间中的收入情况,描述为两个长度为n的整数数组dates和earnings,表示在

hdu 1011(树形dp)

Mark.看着吴神博客写的,还未完全懂. 1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 #include <set> 8 #include <map> 9 #include <string>