UVA 11552——Fewest Flops

谁借莪１个温暖的怀抱￠ 2022-07-28 01:21 80阅读 0赞

题意：给定一个长为s的字符串（其中s为k的倍数），然后按照前后分成s/k 组，每组之内可以重排，使得重排后的块数最少（一段连续的字母算是一块）。

思路：区间dp，dp\[i\]\[fa\]表示前i组且第i+1组的最左边的字符是fa+'a'的状态能得到的最少的块数,那么状态转移也就是枚举两边应该放什么字符。

code：

#include <bits/stdc++.h>
    using namespace std;
    
    const int N=1005;
    vector<int>g[N];
    int n,k,dp[N][26];
    char s[N];
    
    int dfs(int i,int j)
    {
        if (dp[i][j]>=0) return dp[i][j];
        if (i==0) return 0;
        vector<int>& v=g[i];
        int ans=INT_MAX;
        for (int k=0;k<v.size();k++){
            int cnt=v.size();
            if (v[k]==j) cnt--;
            for (int p=0;p<v.size();p++)
                ans=min(ans,dfs(i-1,v[p])+cnt+(p==k&&v.size()>1?1:0));
        }
        return dp[i][j]=ans;
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while (T--){
            scanf("%d%s",&k,&s);n=0;
            for (int i=0;s[i]!='\0';i+=k){
                char s1[N];
                for (int j=i;j<i+k;j++) s1[j-i]=s[j];s1[k]='\0';
                sort(s1,s1+k);
                g[++n].clear();
                for (int j=0;j<k;j++)
                    if (s1[j]!=s1[j+1])
                    g[n].push_back(s1[j]-'a');
            }
            memset(dp,-1,sizeof(dp));
            printf("%d\n",dfs(n,26));
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，80人围观）

还没有评论，来说两句吧...

相关阅读

相关【计算机视觉】GFLOPs、FLOPS和FLOPs的区别和联系（含代码示例）

文章目录一、GFLOPs、FLOPs、FLOPS 二、单位换算三、如何计算FLOPs 四、计算示例这三个概念其实都差不多，都涉及浮点

红太狼/ 2024年02月05日 20:00/ 0 赞/ 37 阅读

相关【题目记录】——POJ 3260 The Fewest Coins 混合背包

POJ 3260 The Fewest Coins 题目地址【[POJ 3260 The Fewest Coins][]】题意：John要去买价值为m的商品. 现在

末蓝、/ 2022年09月02日 05:16/ 0 赞/ 89 阅读

相关 UVA 11552——Fewest Flops

题意：给定一个长为s的字符串（其中s为k的倍数），然后按照前后分成s/k 组，每组之内可以重排，使得重排后的块数最少（一段连续的字母算是一块）。思路：区间dp，d

谁借莪１个温暖的怀抱￠/ 2022年07月28日 01:21/ 0 赞/ 81 阅读

相关如何计算flops

这里FLOPs (FLoating-point Operations Per Second)是衡量浮点性能的常用单位，即每秒做的浮点运算次数。它常被用来估算电脑的执行效能，尤其

电玩女神/ 2022年01月23日 00:05/ 0 赞/ 550 阅读

相关 CNN模型所需的计算力（flops）以及常见层的flops分析

1、flops解释 Flops: floating point operations per second的缩写，指的是每秒浮点运算次数，理解为计算速度。是一个衡量硬件性能的

﹏ヽ暗。殇╰゛Y/ 2021年12月21日 15:59/ 0 赞/ 663 阅读

相关 UVA 11552 Fewest Flops（序列划分模型；状态设计）

题意：给一个正整数k和字符串s，s的长度是k的倍数，把s每k个字符分成一组，没组之间的字符可以任意重排，但组与组之间的顺序保持不变。任务是让重排后的新字符串s'的块最少，连续

冷不防/ 2021年12月12日 16:07/ 0 赞/ 142 阅读

相关 UVA 414

include<iostream> include<string> include<cstring> using namespace std;

╰半夏微凉°/ 2021年11月17日 21:36/ 0 赞/ 257 阅读

相关 UVA 488

include<stdio.h> long abs(long x) { return x>0?x:-x; } int m

左手的ㄟ右手/ 2021年11月17日 21:34/ 0 赞/ 226 阅读

相关 UVA 621

include<iostream> include<string> using namespace std; int main() {

朴灿烈づ我的快乐病毒、/ 2021年11月17日 21:33/ 0 赞/ 212 阅读

相关 Uva 540

include<iostream> include<queue> include<cstring> include<string> us

Love The Way You Lie/ 2021年11月17日 21:20/ 0 赞/ 296 阅读