编译器推荐
CP Editor
一款专门为竞赛用的编译器。起初我用过最基础的devc++，之后是code::block,然后用sublime text3 ,后来研究vs code，但是值的青睐的是CP Editor 能够直接连接网站，直接提交CodeFoces，还可以部分竞赛网站的样例。这就很奈斯。但是还是有缺点的，比如自动对齐，格式化，高亮，错误提醒。但是这些跟连接网站会直接提交比起来都是小事，CP Editor可以生成模板。
如果要高亮可以看下面这款
Sublime text3
短小精悍，高亮很爱，自动对齐，格式化，插件可以让你满意。还有错误提醒有时候会在代码上直接跳出错误，有人说会打乱思路，有时实在底部弹出错误。还有就是不能连接网站。这点CP Editor可以。但是不得不说Sublime text3的插件真的很好，高亮超棒，而且可以打开大数据文件。
在说一下传统的Code：：block和devc++
Code::block，devc++
适合新手，编译运行，能到很直观的错误。轻便，没有上面那两个的杂七杂八的东西。关键是简单易操作。但是我是个追求“艺术美”的人，就爱瞎鼓捣。不安分。
vs code 没有太懂，就不列举了。
上述的编译器，在windows系统上都有，linux系统上好像没有devc++其他都有。mac不清楚。
题意:
给出你H × W地区,每个坐标(i,j) 表示一个城市,每个城市建造基站都需要成本a[i][j],然后你需要选择两个不同的城市,为其建立基站,并且连上网,每单位距离花费C 并且连点的距离为曼哈顿距离 ,也就是两坐标的差的绝对值的和.|i-x|+|j-y|.让你求成本最小为多少?
思路：
这个地方需要用到类似二维最值这个知识点，用来维护点最优．
我们先从头分析一下，我们需要两个基站，那么代价一定是$a{i,j}+a{x,y}$ 他们之间的网需要C*(|i-x|+|j-y|);
如果我们规定平面图形是这样的：
加设左上角大，右下角小．
- 那么就有两种情况：
- $i≥x,j≥y 这样我们就可以去掉绝对值 变成Ci+Cj-Cx-C*y$ 其实就是将每个点为坐标与其代价链接到一起
- i≥x,j<y 这样我们就转换一个负代价一个正代价结合
之后就是终点看他这个二维最值
其实就是把代价最少点一直递归上去．
// Problem: D - National Railway
// Contest: AtCoder - AtCoder Beginner Contest 210
// URL: https://atcoder.jp/contests/abc210/tasks/abc210_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
#define x first
#define y second
#define sf scanf
#define pf printf
#define PI acos(-1)
#define inf 0x3f3f3f3f
#define lowbit(x) ((-x)&x)
#define mem(a,x) memset(a,x,sizeof(a))
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
#define debug(x) cout << #x << ": " << x << endl;
const int MOD = 998244353;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
const int dx[] = {0, 1, -1, 0, 0};
const int dy[] = {0, 0, 0, 1, -1};
const int dz[] = {1, -1, 0, 0, 0, 0 };
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
ll h,c,w;
ll a[1010][1010],b[1010][1010],d[1010][1010];
void solve()
{
scanf("%lld%lld%lld",&h,&w,&c);
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
scanf("%lld",&a[i][j]);
b[i][j]=a[i][j]+c*(i+j);
d[i][j]=(1ll<<60);
}
}
ll ans=(1ll<<60);
for(int j=w-1;j>=1;j--){
ll num=b[h][j+1];
d[h][j]=num+a[h][j]-c*(h+j);
b[h][j]=min(b[h][j],num);
ans=min(ans,d[h][j]);
}
for(int i=h-1;i>=1;i--){
ll num=b[i+1][w];
d[i][w]=num+a[i][w]-c*(i+w);
b[i][w]=min(b[i][w],num);
ans=min(ans,d[i][w]);
}
for(int i=h-1;i>=1;i--){
for(int j=w-1;j>=1;j--){
ll num1 = b[i+1][j];
ll num2 = min(num1,b[i+1][j+1]);
ll num3 = min(num2,b[i][j+1]);
d[i][j]=num3 + a[i][j]-c*(i+j);
b[i][j]=min(b[i][j],num3);
ans=min(ans,d[i][j]);
}
}
/**left**/
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
b[i][j]=a[i][j]+c*(i-j);
d[i][j]=(1ll<<60);
}
}
for(int j=2;j<=w;j++){
ll num=b[h][j-1];
d[h][j]=num+a[h][j]-c*h+c*j;
b[h][j]=min(b[h][j],num);
ans=min(ans,d[h][j]);
}
for(int i=h-1;i>=1;i--){
ll num=b[i+1][1];
d[i][1]=num+a[i][1]-c*i+c*1;
b[i][1]=min(b[i][1],num);
ans=min(ans,d[i][1]);
}
for(int i=h-1;i>=1;i--){
for(int j=2;j<=w;j++){
ll num1 = b[i+1][j];
ll num2 = min(num1,b[i+1][j-1]);
ll num3 = min(num2,b[i][j-1]);
d[i][j]=num3 + a[i][j]-c*i+c*j;
b[i][j]=min(b[i][j],num3);
ans=min(ans,d[i][j]);
}
}
cout<<ans<<endl;
}
int main()
{
ll t = 1;
///scanf("%lld",&t);
while(t--)
{
solve();
}
return 0;
}
