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$可行。

所以可以记$dp[i][j]$表示,第$i$位至第$\frac{n}{2}$位,$dis$为$j$是否可以被凑出,倒着$dp$一下就可以了。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0),eps=1e-6;
void File()
{
    freopen("D:\\in.txt","r",stdin);
    freopen("D:\\out.txt","w",stdout);
}
template <class T>
inline void read(T &x)
{
    char c=getchar(); x=0;
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) {x=x*10+c-‘0‘; c=getchar();}
}

const int maxn=1010;
char s[maxn],ans[maxn];
int T,n,m;
int a[maxn],b[maxn];
bool dp[510][maxn];

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        memset(dp,0,sizeof dp);
        scanf("%d%d",&n,&m);

        scanf("%s",s);

        for(int i=1;i<=n/2;i++) a[i]=s[i-1]-‘a‘+1;
        for(int i=n/2;i<=n-1;i++) b[i-n/2+1]=s[i]-‘a‘+1;

        dp[n/2+1][0]=1;
        for(int i=n/2;i>=1;i--)
        {
            if(a[i]==b[i])
            {
                for(int j=0;j<=1000;j++) dp[i][j]=dp[i+1][j];
                for(int j=0;j<=1000;j++) if(dp[i+1][j]==1&&j+2<=1000) dp[i][j+2]=1;
            }

            else
            {
                for(int j=0;j<=1000;j++)
                {
                    if(dp[i+1][j]==1)
                    {
                        if(j+1<=1000) dp[i][j+1]=1;
                        if(j+2<=1000) dp[i][j+2]=1;
                    }
                }
            }
        }

        bool fail=0; int z=m;
        for(int i=1;i<=n/2;i++)
        {
            bool xx=1;
            for(int j=1;j<=26;j++)
            {
                int num=0;
                if(a[i]!=j) num++; if(b[i]!=j) num++;

                if(z-num<0) continue;
                if(dp[i+1][z-num])
                {
                    ans[i]=j;
                    xx=0; z=z-num; break;
                }
            }
            if(xx==1) fail=1;
            if(fail==1) break;
        }

        if(fail) printf("Impossible\n");
        else
        {
            for(int i=1;i<=n/2;i++) printf("%c",ans[i]-1+‘a‘);
            for(int i=1;i<=n/2;i++) printf("%c",ans[i]-1+‘a‘);
            printf("\n");
        }
    }
    return 0;
}
时间: 09-22

HDU 5903 Square Distance的相关文章

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 distanc

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 1518 Square (dfs搜索可参考poj1011)

Square Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8589    Accepted Submission(s): 2784 Problem Description Given a set of sticks of various lengths, is it possible to join them end-to-end

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

链接:hdu 1398 题意:有17种货币,面额分别为i*i(1<=i<=17),都为无限张, 给定一个值n(n<=300),求用上述货币能使价值总和为n的方案数 分析:这题可以用母函数的思想,对300以内的值进行预处理即可 也可用完全背包思想求300以内的方案数 母函数: #include<stdio.h> int main() { int c1[305],c2[305],i,j,k,n; for(i=0;i<=300;i++){ c1[i]=1; c2[i]=0;

HDU 1398 Square Coins

http://acm.hdu.edu.cn/showproblem.php?pid=1398 大概像是01背包 #include<bits/stdc++.h> using namespace std; const int maxn = 400; int dp[maxn]; int s[maxn]; void init() { memset(dp,0,sizeof(dp)); } int main () { int n; for(int i=1;i<=17;i++) s[i] = i*i;

HDU 4712 Hamming Distance (随机函数)

Hamming Distance Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 1806    Accepted Submission(s): 714 Problem Description (From wikipedia) For binary strings a and b the Hamming distance is equal

hdu 1518 Square

Problem Description Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square? Input The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number

hdu 1398 Square Coins(生成函数,完全背包)

pid=1398">链接:hdu 1398 题意:有17种货币,面额分别为i*i(1<=i<=17),都为无限张. 给定一个值n(n<=300),求用上述货币能使价值总和为n的方案数 分析:这题能够用母函数的思想,对300以内的值进行预处理就可以 也可用全然背包思想求300以内的方案数 母函数: #include<stdio.h> int main() { int c1[305],c2[305],i,j,k,n; for(i=0;i<=300;i++){

hdu 2736 Average distance

传送门 Average distance Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 682    Accepted Submission(s): 244Special Judge Problem Description Given a tree, calculate the average distance between two