Problem B. 即時戰略 (rts.c/cpp/pas)
注意
Input file: rts.in
Output file: rts.out
Time Limit : 2 seconds
Memory Limit: 512 megabytes
題面
\(\text{HLY}\)在玩一個即時戰略\(\text{(Real Time Strategy)}\)游戲，與大多數同類游戲類似，這個游戲的地圖是平面的，并且玩家都有一個基地，
\(\text{HLY}\)的對手杰哥的基地是一個\(w \times h\)的矩形，其中矩形的每個格子都有一個建筑，每個建筑都有一個重要度，其中第\(i\)行第\(j\)列的格子中的建筑的重要度為\(w_{ij}\)，
\(\text{HLY}\)決定轟炸杰哥的基地，他可以選擇杰哥基地的任何一個格子釋放一個能量為\(p\)的炸彈，釋放以后，這個格子的建筑會受到\(p\)的摧毀度，炸彈產生的沖擊波可以向四個方向擴散，每擴散一格能量值會減少\(1\)，即釋放位置相鄰的\(4\)個格子會受到\(p ? 1\)的摧毀度，再向外的\(8\)個格子會受到\(p ? 2\)的摧毀度 ... 直到能量值減為 \(0\) ，形式化的講，如果在第 \(x\) 行第 \(y\) 列釋放炸彈，那么第 \(i\) 行第$ j$ 列的格子受到的摧毀度 $d_{ij} = max(0,p ? (| x ? i | + | y ? j |)) $，
對于每個的格子，杰哥受到的損失即為這個格子的重要度與受到的摧毀度的乘積，即\(w_{ij} \times d_{ij}\)，
\(\text{HLY}\)想知道，對于每一種投放炸彈的方案，杰哥受到的最小總損失和最大總損失各為多少，形式化的講，即為
\[\large \sum_{i=1}^{w}\sum_{j=1}^{h} w_{ij} \times d_{ij} \]的最小值與最大值，
輸入格式
第\(1\)行三個整數\(w,h,p\)，
接下來\(w\)行，每行\(h\)個整數，從第\(2\)行開始第\(i\)行第\(j\)個整數表示\(w_{ij}\)，
輸出格式
一行兩個數，表示杰哥受到的最小總損失和最大總損失，用空格隔開，
樣例
\(\texttt{input\#1}\)
3 4 3
9 9 9 1
9 9 1 1
9 1 1 1
\(\texttt{output\#1}\)
10 96
資料范圍與提示
樣例解釋：
\(\text{HLY}\)在第\(2\)行第\(2\)列釋放炸彈杰哥所受損失最大，為
\(9 \times 1 + 9 \times 2 + 9 \times 1 + 9 \times 2 + 9 \times 3 + 1 \times 2 + 1 \times 1 + 9 \times 1 + 1 \times 2 + 1 \times 1 = 96\)，
\(\text{HLY}\)在第\(3\)行第\(4\)列釋放炸彈杰哥所受損失最小， 為
\(1\times1+1\times1+1\times2+1\times1+1\times2+1\times3 = 10\)，
對于\(100%\)的資料，\(1 \le n,m \le 400,1 \le p \le 200,0 \le w ij \le 10^5\)，
子任務\(1\)（\(10\)分） ：滿足\(p= 1\)，
子任務\(2\)（\(30\)分） ：滿足\(1 \le n,m \le 40\)，
子任務\(3\)（\(60\)分） ：沒有特殊限制，
題解
\(1 \le n,m \le 400\)模擬可過，不過需要點技巧——前綴和，
一個能量為\(3\)的炸彈產生的影響如上圖，
很明顯是\(3\)個菱形，我們計算每個菱形的邊加到一起，
但暴力加明顯過不了，所以使用前綴和，維護一個從左上到右下的前綴和以及一個從右上到坐下的前綴和（是一條線上的），
具體看代碼，
\(Code\)
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
#define MAXN 2020
#define int long long
int w,h,p,ans1=0,ans2=1e18,map[MAXN][MAXN];
int sum1[MAXN][MAXN],sum2[MAXN][MAXN];
inline void read(int &T) {
int x=0;bool f=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
T=f?-x:x;
}
signed main() {
read(w),read(h),read(p);
w+=500,h+=500;//防止越界
for(int i=501;i<=w;++i) {
for(int j=501;j<=h;++j) {
read(map[i][j]);
}
}
for(int i=1;i<=2010;++i) {
for(int j=1;j<=2010;++j) {
sum1[i][j]=sum1[i-1][j-1]+map[i][j];
}
}//一個從左上到右下的前綴和
for(int i=1;i<=2010;++i) {
for(int j=2010;j>=1;--j) {
sum2[i][j]=sum2[i-1][j+1]+map[i][j];
}
}//一個從右上到左下的前綴和
for(int i=501;i<=w;++i) {
for(int j=501;j<=h;++j) {//列舉將炸彈放到哪一個點
int sum=p*map[i][j];
int x=p;
while(x>1) {
sum+=(p-x+1)*(sum1[i][j+x-1]-sum1[i-x][j-1]);
sum+=(p-x+1)*(sum1[i+x-1][j]-sum1[i-1][j-x]);
sum+=(p-x+1)*(sum2[i][j-x+1]-sum2[i-x][j+1]);
sum+=(p-x+1)*(sum2[i+x-1][j]-sum2[i-1][j+x]);
sum-=(p-x+1)*map[i-x+1][j];
sum-=(p-x+1)*map[i+x-1][j];
sum-=(p-x+1)*map[i][j-x+1];
sum-=(p-x+1)*map[i][j+x-1];
--x;
}//計算放到該點的摧毀度
ans1=max(ans1,sum);
ans2=min(ans2,sum);
}
}
std::cout<<ans2<<" "<<ans1<<'\n';
return 0;
}
上接【CSP-S膜你考】最近公共祖先 （數學）
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/96296.html
標籤：C++
上一篇：兩個數的差