hdu 5903 Square Distance

这题题解dp不懂 因为不知道它怎么记录dp的答案的 字符串那么长
我是贪心过得,当时还被四个人hack,都没成功,hhhhh
大意就是优先从头取字典序小的字母,担也要让后面不管怎么取都合法

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e3+5;
int N,M;
char S[MAXN];
char ans[MAXN];
int tg[MAXN];

int ju(int x,int y,int c) {
//    printf("%d %d %d
",x,y,c);
    if(c < 0) return 0;
    if(x == 0) {
        if(c%2 || c > y*2) return 0;
    }else if(c > (x+y)*2 || c < x) return 0;
//    printf("got
");
    return 1;
}
int main(){
    int T; scanf("%d",&T);
    while(T--) {
        scanf("%d %d",&N,&M);
        scanf("%s",S+1);

        int c1 = 0; int c2 = 0;
        for(int i = 1; i <= N/2; ++i) {
            if(S[i] > S[i+N/2]) swap(S[i], S[i+N/2]);
            if(S[i] != S[i+N/2]) tg[i] = 1, c1 ++;
            else tg[i] = 2, c2 ++;
        }

        if(c1==0) {
            if(M%2 || M>c2*2) {
                printf("Impossible
"); continue;
            }
        }else if(M > (c2+c1)*2 || M < c1) {
            printf("Impossible
"); continue;
        }


        for(int i = 1; i <= N/2; ++i) {
            char t1= S[i]; char t2= S[i+N/2];
            if(tg[i] == 1) {
                if(t1 == 'a') {
                    if(ju(c1-1,c2,M-1)) ans[i] = 'a', M--;
                    else {
                        if(t2 == 'b') ans[i] = 'c', M-=2;
                        else ans[i] = 'b', M-=2;
                    }
                }else {
                    if(ju(c1-1,c2,M-2)) ans[i] = 'a', M-=2;
                    else ans[i] = min(t1,t2), M--;
                }
                c1--;
            }else {
                if(t1 == 'a'){
                    if(ju(c1,c2-1,M)) ans[i] = 'a';
                    else ans[i] = 'b', M-=2;
                }else {
                    if(ju(c1,c2-1,M-2)) ans[i] = 'a', M-=2;
                    else ans[i] = t1;
                }
                c2--;
            }            
        }

        for(int i = 0; i < 2; ++i)
            for(int j = 1; j <= N/2; ++j)
                printf("%c",ans[j]); printf("
");
    }
    return 0;
}