題目鏈接

我用的比較傳統(tǒng)的辦法。。。單調(diào)隊(duì)列優(yōu)化了一下，寫(xiě)的有點(diǎn)搓，不管怎樣過(guò)了。。。兩個(gè)單調(diào)隊(duì)列，存兩個(gè)東西，預(yù)處理一個(gè)標(biāo)記數(shù)組存。。。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <map> 6 #include <ctime> 7 #include <cmath> 8 #include <algorithm> 9 using namespace std; 10 #define INF 1000000 11 char str[200000]; 12 int dp[200000]; 13 int pre[200000]; 14 int que1[200000]; 15 int que2[200000]; 16 int judge(char s) 17 { 18 if(s <= 'Z'&&s >= 'A') 19 return 1; 20 else if(s <= 'z'&&s >= 'a') 21 return 1; 22 else if(s == ' ') 23 return 1; 24 else 25 return 0; 26 } 27 int main() 28 { 29 int n,m,i,j,len,str1,end1,str2,end2; 30 scanf("%d%d%*c",&n,&m); 31 gets(str); 32 len = strlen(str); 33 for(i = 0; i < len; i ++) 34 { 35 if(judge(str[i])) 36 { 37 for(j = i; j < len; j ++) 38 { 39 if(judge(str[j])) 40 pre[j] = i; 41 else 42 { 43 i = j; 44 break; 45 } 46 } 47 if(j == len) break; 48 } 49 } 50 for(i = 1;i <= len;i ++) 51 dp[i] = INF; 52 str1 = 0;end1 = 1; 53 str2 = 0;end2 = 1; 54 que1[0] = que2[0] = 0; 55 for(i = 1;i <= len;i ++) 56 { 57 dp[i] = dp[que1[str1]] + 1; 58 if(judge(str[i-1])) 59 { 60 if(str2 < end2) 61 dp[i] = min(dp[i],dp[que2[str2]]+1); 62 } 63 else 64 { 65 str2 = end2 = 0; 66 } 67 if(i == len) continue; 68 while(str1 < end1&&dp[i] <= dp[que1[end1-1]]) 69 end1 --; 70 que1[end1++] = i; 71 while(str1 < end1&&i - que1[str1] >= n) 72 str1 ++; 73 if(judge(str[i])) 74 { 75 while(str2 < end2&&dp[i] <= dp[que2[end2-1]]) 76 end2 --; 77 que2[end2++] = i; 78 while(str2 < end2&&que2[str2] < pre[i]) 79 str2 ++; 80 while(i - que2[str2] >= m&&str2 < end2) 81 str2 ++; 82 } 83 } 84 printf("%d\n",dp[len]); 85 return 0; 86 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/naix-x/p/3315207.html

總結(jié)

以上是生活随笔為你收集整理的URAL 1427. SMS(DP+单调队列)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。