[COCI 2009/2010 – Constest #7 KRALJEVI]矩阵上的各种维护 & 分类讨论

【题目地址】http://evaluator.hsin.hr/login.php?redirect=index.php
【题目大意】
在一个m*n的矩阵里，给出一些国际象棋中的王，让你求出所有王对（。。。就是那些点对）之间最小到达步数的和。
【算法分析】
设
LU[i][j]表示以（i，j）为右下角的这个矩形内的所有的王跳到(i，j)这个位置一共跳了多少步。
LS[i][j]表示以（i，j）为右下角的这个矩形内的所有的王的数目。
RU[i][j]和RS[i][j]同上。
UU[i][j]表示以从(1，j)到（i，j）这一路下来的王跳到（i，j）一共跳的步数。
US[i][j]表示以从(1，j)到（i，j）这一路下来一共有多少个王。

然后就是设法维护一下，像dp一样，并不是很难。
【CODE】
#include #include #include long long LU[1005][1005],RU[1005][1005],UU[1005][1005];
int LS[1005][1005],RS[1005][1005],US[1005][1005];
char c[1005][1005];

void init(){
scanf("%d%d",&m,&n);
for (int i=1;i<=m;i++)
scanf("%s",&c[i][1]);
}

void solve(){
int i,j;
memset(LS,0,sizeof(LS));
memset(RS,0,sizeof(RS));
memset(LU,0,sizeof(LU));
memset(RU,0,sizeof(RU));

long long ans=0;
for (i=1;i<=m;i++){
for (j=1;j<=n;j++){
LU[i][j]=LU[i][j-1]+LS[i][j-1];
LS[i][j]=LS[i][j-1];
if (c[i][j]==’M’){
LS[i][j]++;
ans+=LU[i][j];
}
}
for (j=n;j>=1;j–){
RU[i][j]=RU[i][j+1]+RS[i][j+1];
RS[i][j]=RS[i][j+1];
if (c[i][j]==’M’) RS[i][j]++;
}
for (j=1;j<=n;j++){
UU[i][j]=UU[i-1][j]+US[i-1][j];
US[i][j]=US[i-1][j];
if (c[i][j]==’M’){
US[i][j]++;
ans+=UU[i][j];
}
}

for (j=1;j<=n;j++){
if (c[i][j]==’M’)
ans+=LU[i-1][j-1]+LS[i-1][j-1]+RU[i-1][j+1]+RS[i-1][j+1];
LU[i][j]+=LU[i-1][j-1]+LS[i-1][j-1]+UU[i-1][j]+US[i-1][j];
LS[i][j]+=LS[i-1][j-1]+US[i-1][j];
RU[i][j]+=RU[i-1][j+1]+RS[i-1][j+1]+UU[i-1][j]+US[i-1][j];
RS[i][j]+=RS[i-1][j+1]+US[i-1][j];
}
}

printf("%lld",ans);
}

int main(){
init();
solve();
printf(" ");
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++){
if (c[i][j]==’M’) c[i][j]=’.’;
if (c[i][j]==’S’) c[i][j]=’M’;
}
solve();
printf("n");
}