uva 11552 Fewest Flops 线性dp-白红宇

uva 11552 Fewest Flops 线性dp

阅读量：4963 次

发布时间：2019-06-12

本文共 2175 字，大约阅读时间需要 7 分钟。

// uva 11552 Fewest Flops//// 二维线性dp//// 首先，在该块必须是相同的来信。首先记录每块有很多种书// 称为是counts[i];// // 订购f[i][j]它代表前i字母j为结尾的最小分块数//// 假设第i块的開始字母与第i-1块的结束字母同样// f[i][j] = min(f[i][j],f[i-1][k] + counts[i] - 1);// // 否则// // f[i][j] = min(f[i][j],f[i-1][k] + counts[i]);//// 第一种情况的開始和结束字母同样有个前提：// f[i-1][k]中的k在第i块中出现//// 之后的条件是：// 1)第i块仅仅有一种字符// 2)第i块结束字符与第i-1块结束字符不同样//// ps：第一种情况是另外一种情况的特殊，由于每种字母要么是在開始，// 要么是在结束，不会连续的两个块结束字母同样，这样肯定不是// 最优的，而假设第i块仅仅有一种字符。那么显然不在这之列。//// wrong answer了10次。如此顽强我也是醉了//// 继续练吧#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         
                          #include 
                          
                           #define ceil(a,b) (((a)+(b)-1)/(b))#define endl '\n'#define gcd __gcd#define highBit(x) (1ULL<<(63-__builtin_clzll(x)))#define popCount __builtin_popcountlltypedef long long ll;using namespace std;const int MOD = 1000000007;const long double PI = acos(-1.L);const int maxn = 1008;const int inf = 0x3f3f3f3f;char s[maxn];bool vis[maxn][30];int f[maxn][300];int n,k;int counts[maxn];void dp(){ for (int i=0;i<=26;i++){ if (vis[1][i]){ f[1][i] = counts[1]; } } for (int i=2;i<=n/k;i++){ for (int j=0;j<26;j++){ if (vis[i][j]){ for (int m=0;m<26;m++){ if (vis[i][m] && (counts[i]==1 || j!=m)){ f[i][j] = min(f[i][j],f[i-1][m] + counts[i] - 1); }else{ f[i][j] = min(f[i][j],f[i-1][m] + counts[i]); } } } } } int ans = inf; for (int i=0;i<26;i++){ ans = min(ans,f[n/k][i]); } printf("%d\n",ans);}void print(){ for (int i=1;i<=n/k;i++){ cout << counts[i] << " "; } cout << endl;}void init(){ scanf("%d %s",&k,s+1); n = strlen(s+1); memset(vis,0,sizeof(vis)); memset(f,inf,sizeof(f)); memset(counts,0,sizeof(counts)); int x=1; for (int i=1;i<=n;i++){ if (!vis[x][s[i]-'a']){ counts[x]++; vis[x][s[i]-'a'] = 1; } if (i%k==0){ x++; } }// cout << "x = " << x << endl;// print(); dp();}int main() { int t; //freopen("E:\\Code\\1.txt","r",stdin); scanf("%d",&t); while(t--){ init(); } return 0;}