字母交换

题目描述

【编码题】字符串S由小写字母构成，长度为n。定义一种操作，每次都可以挑选字符串中任意的两个相邻字母进行交换。询问在至多交换m次之后，字符串中最多有多少个连续的位置上的字母相同？

输入描述:

第一行为一个字符串S与一个非负整数m。(1 <= |S| <= 1000, 1 <= m <= 1000000)

输出描述:

一个非负整数，表示操作之后，连续最长的相同字母数量。

示例1

输入

abcbaa 2

输出

2

说明

使2个字母a连续出现，至少需要3次操作。即把第1个位w置上的a移动到第4个位置。
所以在至多操作2次的情况下，最多只能使2个b或2个a连续出现。

思路:

动态规划递推公式 dp【i】[j]= dp【i+1】【j-1】 + a[j]-a[i] -(j-i);,计算时只算上三角情况，每个字母单独计算，递归公式看懂就会做了。第一轮计算相邻相同字母的相邻距离，第二轮计算相差两个位置的字母靠近需要多少距离

上三角举例

0111

0011

0001

代码:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int max(int a,int b){
    return a>b?a:b;
}
int main(){
    char s[10001];
    int m,max_seq;
    scanf("%s%d",s,&m);
    int size_s = strlen(s);
    for(char c ='a';c<='z' ; c++){
        int *a = (int *)malloc(sizeof(int)*10002);
        int size =0;
        for(int i=0;i<size_s;i++){
            //把相同字符的位置求出来
            if(s[i] ==c) a[size++] = i;
        }
        if(size){
            int dp[1002][1001];
            memset(dp,0,sizeof(dp));
            int seq = 1;
            //只计算上三角情况
            for(int r=1;r<size;r++){
                for(int i=0;i<size-r;i++){
                    int j = i+r;
                    // 在第一轮的情况下
                    if(j==i+1){
                        dp[i][j] = a[j]-a[i]-1;
                    }else{
                        dp[i][j] = dp[i+1][j-1] + a[j]-a[i] -(j-i);
                    }
                    if(dp[i][j]<=m)
                        seq = max(seq,j-i+1);
                }
            }
            max_seq = max(max_seq,seq);
        }
    }
    printf("%d\n",max_seq);
}

代码效率：

运行时间：11ms, 超过57.14%用C提交的代码
占用内存：4348KB, 超过40.00%用C提交的代码