USACO 2023 January Silver Problem 2 Following Directions (二维数组递推
#include<bits/stdc++.h>
//pass all TC, 二维递推路径节点数，更改节点方向只需要顺新旧方向分别加减节点数
using namespace std;
typedef long long ll;
const int MAX=1502;
char mat[MAX][MAX];
int d[MAX][MAX];//vetex count
vector<int> rvat(MAX),bvat(MAX);
void printd(int n){
for(int i=1;i<=n+1;i++){
for(int j=1;j<=n+1;j++){
cout<<d[i][j]<<" ";
}
cout<<endl;
}
}
ll findsum(int n){
ll res=0;
for(int i=1;i<=n;i++){
res+=d[i][n+1]*rvat[i];
res+=d[n+1][i]*bvat[i];
}
return res;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
string ts;
cin>>ts;
cin>>rvat[i];
for(int j=1;j<=n;j++){
mat[i][j]=ts[j-1];
d[i][j]=1;
}
}
for(int i=1;i<=n;i++){
cin>>bvat[i];
}
for(int i=1;i<=n+1;i++){
for(int j=1;j<=n+1;j++){
if(mat[i-1][j]=='D'){
d[i][j]+=d[i-1][j];
}
if(mat[i][j-1]=='R'){
d[i][j]+=d[i][j-1];
}
}
}
//printd(n);
cout<<findsum(n)<<endl;
int q;
cin>>q;
while(q>0){
q--;
int a,b;
cin>>a>>b;
int x=a,y=b;
while(x<=n&&y<=n){
if(mat[x][y]=='D'){
d[x+1][y]-=d[a][b];
x++;
}else{
d[x][y+1]-=d[a][b];
y++;
}
}
if(mat[a][b]=='D'){
mat[a][b]='R';
}else{
mat[a][b]='D';
}
x=a;y=b;
while(x<=n&&y<=n){
if(mat[x][y]=='D'){
d[x+1][y]+=d[a][b];
x++;
}else{
d[x][y+1]+=d[a][b];
y++;
}
}
//printd(n);
cout<<findsum(n)<<endl;
}
return 0;
}
