daimayuan 国家铁路(前缀和,dp)代码源

简介: daimayuan 国家铁路(前缀和,dp)代码源

1.首先答案必定为A [ x 1 , y 1 ] + A [ x 2 , y 2 ] + C ∗ ( ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ ) A[x_1,y_1]+A[x_2,y_2]+C*(|x_1-x_2|+|y_1-y_2|)A[x1,y1]+A[x2,y2]+C(x1x2+y1y2)

2.我们想办法去掉绝对值,给选择的两个点规定方向,分别是一个点在左下,一个点右上;一点左上,一个点右下(方向是两个点的相对方向)。

1.当左下右上时,维护 m 1 [ i ] [ j ] m_1[i][j]m1[i][j] 为左下角到i , j i,ji,j的最小的 C ∗ ( i − j ) + A [ i , j ] C*(i-j)+A[i,j]C(ij)+A[i,j]

因为如果这个方案取到答案:

a n s = A [ x 1 , y 1 ] + A [ x 2 , y 2 ] + C ∗ ( y 2 − y 1 + x 1 − x 2 ) ( x 1 , y 1 左 下 , x 2 , y 2 右 上 ) 。 ans=A[x_1,y_1]+A[x_2,y_2]+C*(y_2-y_1+x_1-x_2)(x_1,y_1左下,x_2,y_2右上)。ans=A[x1,y1]+A[x2,y2]+C(y2y1+x1x2)(x1,y1x2,y2)

变换得a n s = A [ x 2 , y 2 ] + C ∗ ( y 2 − x 2 ) + A [ x 1 , y 1 ] + C ( x 1 − y 1 ) ans=A[x_2,y_2]+C*(y_2-x_2)+A[x_1,y_1]+C(x_1-y_1)ans=A[x2,y2]+C(y2x2)+A[x1,y1]+C(x1y1),我们令m 1 [ i , j ] = A [ i , j ] + C ∗ ( i − j ) m_1[i,j]=A[i,j]+C*(i-j)m1[i,j]=A[i,j]+C(ij),m 1 m_1m1维护最小值。

2.同理当左上右下时,维护 m 2 [ i ] [ j ] m_2[i][j]m2[i][j] 为左上角到i , j i,ji,j的最小的 − C ∗ ( i + j ) + A [ i , j ] -C*(i+j)+A[i,j]C(i+j)+A[i,j]

m 2 [ i , j ] = A [ i , j ] − C ∗ ( i + j ) m_2[i,j]=A[i,j]-C*(i+j)m2[i,j]=A[i,j]C(i+j)。(想不明白画画图)。

维护利用了二维前缀和思想

代码如下

/*********************************************************************
    程序名:
    版权: Joecai
    作者: Joecai
    日期: 2022-04-28 23:56
    说明:
*********************************************************************/
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
# define rep(i,be,en) for(int i=be;i<=en;i++)
# define pre(i,be,en) for(int i=be;i>=en;i--)
#define ll long long
#define endl "\n"
#define LOCAL
#define pb push_back
#define int long long
typedef pair<ll, ll> PII;
#define eb emplace_back
#define sp(i) setprecision(i)
const int N = 1000 + 10, INF = 0x3f3f3f3f;
int h, w, c;
int a[N][N];
int m1[N][N];//维护左下角到i,j的的最小值
int m2[N][N];//维护左上角到i,j的最小值
void solve()
{
  cin >> h >> w >> c;
  memset(m1, 0x3f, sizeof(m1));
  memset(m2, 0x3f, sizeof(m2));
  for (int i = 1; i <= h; i++)
  {
    for (int j = 1; j <= w; j++)
    {
      cin >> a[i][j];
    }
  }
  for (int i = h; i >= 1; i--)
  {
    for (int j = 1; j <= w; j++)
    {
      m1[i][j] = min({a[i][j] + c * (i - j), m1[i + 1][j], m1[i][j - 1]}); //左下到右上
    }
  }
  for (int i = 1; i <= h; i++)
  {
    for (int j = 1; j <= w; j++)
    {
      m2[i][j] = min({a[i][j] - c * (i + j), m2[i - 1][j], m2[i][j - 1]}); //左s上到右下
    }
  }
  int ans = 0x3f3f3f3f3f3f3f3f;
  for (int i = h; i >= 1; i--)
  {
    for (int j = 1; j <= w; j++)
    {
      ans = min(ans, a[i][j] + c * (j - i) + min(m1[i + 1][j], m1[i][j - 1]));
    }
  }
  for (int i = 1; i <= h; i++)
  {
    for (int j = 1; j <= w; j++)
    {
      ans = min(ans, a[i][j] + c * (i + j) + min(m2[i - 1][j], m2[i][j - 1]));
    }
  }
  cout << ans << endl;
}
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  //#ifdef LOCAL
  //freopen("data.in.txt","r",stdin);
  //freopen("data.out.txt","w",stdout);
  //#endif
  int __ = 1;
  //cin>>__;
  while (__--)
  {
    solve();
  }
  return 0;
}

点个赞再走叭~(*σ´∀`)σ

目录
相关文章
Java 通过IP获取对应的国家省份城市经纬度(离线文件方案)
一. 除了调用接口查询城市, 还可以通过离线文件查询城市, 使用GeoLite2 City库 二. 离线库下载地址: https://dev.maxmind.com/geoip/geoip2/geolite2/ 点击如下位置下载压缩文件 文件解压后有一个文件名为GeoLite2-City.
牛客竞赛21670 两条公路 (18951 两条斜线)
牛客竞赛21670 两条公路 (18951 两条斜线)
算法强化每日一题--删除公共字符
算法强化每日一题--删除公共字符
|
定位技术
(枚举)(模拟)(二位前缀和)99. 激光炸弹
(枚举)(模拟)(二位前缀和)99. 激光炸弹
111 0
牛客IOI周赛23-普及组 D.小L的数列 (dp状态+枚举因子)
牛客IOI周赛23-普及组 D.小L的数列 (dp状态+枚举因子)
116 0
|
API
Google Earth Engine——街区数据集包含2010年的人口普查街区,最小单位大致相当于一个城市街区。超过1100万个多边形特征,覆盖美国、哥伦比亚特区、波多黎各和岛屿地区。
Google Earth Engine——街区数据集包含2010年的人口普查街区,最小单位大致相当于一个城市街区。超过1100万个多边形特征,覆盖美国、哥伦比亚特区、波多黎各和岛屿地区。
188 0
Google Earth Engine——街区数据集包含2010年的人口普查街区,最小单位大致相当于一个城市街区。超过1100万个多边形特征,覆盖美国、哥伦比亚特区、波多黎各和岛屿地区。
|
API
Google Earth Engine——美国人口普查局的TIGER数据集包含了2016年发布的所有路段,包含了1900多万条单独的线路特征,覆盖了美国、哥伦比亚特区、波多黎各和岛屿地区
Google Earth Engine——美国人口普查局的TIGER数据集包含了2016年发布的所有路段,包含了1900多万条单独的线路特征,覆盖了美国、哥伦比亚特区、波多黎各和岛屿地区
174 0
Google Earth Engine——美国人口普查局的TIGER数据集包含了2016年发布的所有路段,包含了1900多万条单独的线路特征,覆盖了美国、哥伦比亚特区、波多黎各和岛屿地区
ctfshow-网络迷踪-初学再练( 一座雕像判断军事基地名称)
ctf.show 网络迷踪第4关,题目中只有一座雕像,需要根据雕像提交军事基地的名称,推荐使用谷歌识图,溯源到一篇博客,答案就在文章标题中
751 0
ctfshow-网络迷踪-初学再练( 一座雕像判断军事基地名称)

热门文章

最新文章