杭電第三場賽后補題

1009. Rise in Price

There are n×n cells on a grid, the top-left cell is at (1,1) while the bottom-right cell is at (n,n). You start at (1,1) and move to (n,n). At any cell (i,j), you can move to (i+1,j) or (i,j+1), provided that you don't move out of the grid. Clearly, you will make exactly 2n?2 steps.

When you are at cell (i,j), including the starting point (1,1) and the destination (n,n), you can take all the ai,j diamonds at this cell, and have a chance to raise the price of each diamond by bi,j dollars. You will sell all the diamonds you have with the final price in the end, and your goal is to choose the optimal path that will maximize your profits. Note that initially the price of each diamond is zero, and you have nothing to sell.

題意：給你兩個數(shù)組棒搜，A:(a_ij 代表下標為i,j的鉆石的個數(shù)，bij表示經(jīng)過i可款，j時間可以使單價提高的價格

這一道題比賽中沒有做出來克蚂，開始賽后補題：

本道題看到所求的最大值，所以考慮動態(tài)規(guī)劃摸恍，對于動態(tài)規(guī)劃游盲，我們需要考慮：

• 關于狀態(tài)定義： 表示經(jīng)過下標,鉆石數(shù)量為的單價
• 關于狀態(tài)轉移方程：
• 
• 

但是由于狀態(tài)比較多益缎，所以我們需要對過程中一部分不可能推出最優(yōu)答案的狀態(tài)刪除，以達到減小復雜度的效果欣范，我們知道：

對于時令哟，這個狀態(tài) 就不可能推導出最優(yōu)答案，可以刪除晴竞。因此我們可以用來定義到達下標為的所有狀態(tài)狠半。所以我們可以根據(jù)升序排序，定義一個數(shù)組來存儲所有狀態(tài),每次merge操作插入（第一維）最小的狀態(tài)已维，當插入第二維Price的時候可以刪去前面相同count但是小于待插入元素price的狀態(tài)已日，以此達到刪除不可能最優(yōu)狀態(tài)的效果。具體代碼如下：

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
typedef vector<P>V;
const int N=105;
//pool 維護所有的 <數(shù)量堂鲜，單價> 的狀態(tài)。
int Case,n,m,i,j,k,a[N][N],b[N][N];ll ans;V f[N][N];P pool[1000005];
inline void ext(const P&t){
  //應為merge操作中是小的先進甫恩，pool中最后一個元素一定小于待插入元素的第一維酌予，如果其第二維也小于待插入元素奖慌，直接剔除就可简僧。
  while(m&&pool[m].second<=t.second)m--;
  if(!m||pool[m].first<t.first)pool[++m]=t;
}
inline void merge(const V&A,const V&B,V&C){
  int ca=A.size(),cb=B.size(),i=0,j=0;
  m=0;
  //這里第一維小的先進，保證pool中的第一維是遞增的
  while(i<ca&&j<cb)ext(A[i].first<B[j].first?A[i++]:B[j++]);
  while(i<ca)ext(A[i++]);
  while(j<cb)ext(B[j++]);
  C.resize(m);
  for(i=0;i<m;i++)C[i]=pool[i+1];
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d",&n);
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&a[i][j]);
    for(i=1;i<=n;i++)for(j=1;j<=n;j++)scanf("%d",&b[i][j]);
    //f[i][j]表示到達下標為(i,j)時候取得所有的 <數(shù)量棉姐，單價> 的全部狀態(tài)啦逆。
    //這里的f[i][j][k].first為數(shù)量； second為單價
    f[1][1].resize(1);
    f[1][1][0]=P(a[1][1],b[1][1]);
    for(i=1;i<=n;i++)for(j=1;j<=n;j++){
      if(i==1&&j==1)continue;
      if(i==1)f[i][j]=f[i][j-1];
      else if(j==1)f[i][j]=f[i-1][j];
      //這一步得到f[i][j]的初始狀態(tài),也就是f[i][j]的 <數(shù)量乃坤，單價> 全部狀態(tài)沟蔑。
      //在初始化f[i][j]的過程中，需要剔除 f[i][j][k1].first < f[i][j][k2].second && f[i][j][k2].first < f[i][j][k2].second , 也就是單價小厅须，數(shù)量也小的可以剔除 
      else merge(f[i-1][j],f[i][j-1],f[i][j]);
      for(k=0;k<f[i][j].size();k++){
        f[i][j][k].first+=a[i][j];
        f[i][j][k].second+=b[i][j];
      }
    }
    ans=0;
    //最后對最后一個位置的所有狀態(tài)求總價取最大就是答案食棕。
    for(i=0;i<f[n][n].size();i++)ans=max(ans,1LL*f[n][n][i].first*f[n][n][i].second);
    printf("%lld\n",ans);
  }
}

1010. Road Discount

There are n cities in Byteland, labeled by 1 to n. The Transport Construction Authority of Byteland is planning to construct n?1 bidirectional roads among these cities such that every pair of different cities are connected by these roads directly or indirectly.

The engineering company has offered m possible candidate roads to construct. The i-th candidate road will cost ci dollars, and if it is finally constructed, there will be a road connecting the ui-th city and the vi-th city directly. Fortunately, each road has its discounted price, the i-th of which is di.

The Transport Construction Authority of Byteland can buy at most k roads at their discounted prices. Please write a program to help the Transport Construction Authority find the cheapest solution for k=0,1,2,…,n?1.

題意：就是在最小連通圖問題宣蠕，但是不同的是每條路有原價和折扣價，我們要找出正好包含k條折扣價的路的最小連通圖抢蚀；

我們可以定義表示包含恰好為最小生成樹中使用黑邊的最小邊權和，所以是一個凸函數(shù)唱逢，求出的方法為：

• 選擇參數(shù)c坞古，將每條黑色的邊權加上
• 求出修改邊權后的圖的最小生成樹，令為對應的邊權和织堂，為最小生成樹使用黑邊數(shù)量的最小值奶陈，為最小生成樹使用黑邊數(shù)量的最大值
• 二分找到答案，若滿足,則

所以我們得到題解

#include<cstdio>
#include<algorithm>
using namespace std;
typedef pair<int,int>P;
const int N=1005,M=200005,V=1000;
int Case,n,m,i,f[N];P fl[V*2+5];
struct E{int x,y,w;}a[M],b[M];
inline bool cmp(const E&a,const E&b){return a.w<b.w;}
//getfather函數(shù)
int F(int x){
  return f[x] == x ? x : f[x] = F(f[x]);
}
//union函數(shù)
inline bool merge(int x,int y){
  if(F(x) == F(y)) return 0;
  f[f[x]]=f[y];
  return 1;
}

inline void reduce(E*e){
  //根據(jù)邊權值來排序
  sort(e+1,e+m+1,cmp);
  for(int i=1;i<=n;i++)f[i]=i;
  for(int i=1,cnt=0;i<=m;i++)
    if(merge(e[i].x,e[i].y))
      e[++cnt]=e[i];
}
//查詢函數(shù)
inline P call(int k){
  for(int i=1;i<=n;i++)f[i]=i;
  int A=1,B=1,sum=0,cnt=0;
  while(A<n&&B<n){
    if(a[A].w<=b[B].w+k){
      if(merge(a[A].x,a[A].y))sum+=a[A].w;
      A++;
    }else{
      if(merge(b[B].x,b[B].y))sum+=b[B].w+k,cnt++;
      B++; 
    }
  }
  while(A<n){
    if(merge(a[A].x,a[A].y))sum+=a[A].w;
    A++;
  }
  while(B<n){
    if(merge(b[B].x,b[B].y))sum+=b[B].w+k,cnt++;
    B++;
  }
  return P(sum,cnt);
}
inline int ask(int k){
  for(int i=-V;i<=V;i++) 
    if(fl[i+V].second<=k) 
      return fl[i+V].first-k*i;
  return -1;
}
int main(){
  scanf("%d",&Case);
  while(Case--){
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
      scanf("%d%d%d%d",&a[i].x,&a[i].y,&a[i].w,&b[i].w);
      b[i].x=a[i].x,b[i].y=a[i].y;
    }
    reduce(a);
    reduce(b);
    for(i=-V;i<=V;i++)fl[i+V]=call(i);
    for(i=0;i<n;i++)printf("%d\n",ask(i));
  }
}