[杂题]FZU2190 非提的救赎-白红宇

[杂题]FZU2190 非提的救赎

阅读量：5323 次

发布时间：2019-06-14

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

中文题，题意不多说。

本来感觉很像dp

其实只要从上到下维护单调性就好了

坑是......这个oj......用cin很容易TLE......

1 //#include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 using namespace std;11 typedef long long LL;12 #include 
               
                13 14 struct node15 {16 int val, cnt;17 }S[2005];18 int val[2005][2005];19 char mp[2005][2005];20 int main()21 {22 int n, m;23 while(~scanf("%d%d", &n, &m))24 {25 // memset(val, 0, sizeof(val));26 for(int i=1;i<=n;i++)27 {28 val[i][0]=0;29 scanf("%s", mp[i]+1);30 for(int j=1;j<=m;j++)31 {32 // cin>>mp[i][j];33 val[i][j]=(mp[i][j]=='w')? (val[i][j-1]+1):0;34 }35 }36 LL ans=0;37 for(int j=1;j<=m;j++)38 {39 LL sum=0;40 int head=0;41 for(int i=1;i<=n;i++)42 {43 node t;44 t.val=val[i][j], t.cnt=1;45 while(head && t.val<=S[head-1].val)46 {47 head--;48 sum-=S[head].val*1LL*S[head].cnt;49 t.cnt+=S[head].cnt;50 }51 sum+=t.val*1LL*t.cnt;52 S[head++]=t;53 ans+=sum;54 }55 }56 printf("%I64d\n", ans);57 }58 return 0;59 }