UVA 1169 DP+単調キュー最適化Robotruckゴミ拾いロボット

2969 ワード

タイトル:
1つのロボットは(0,0)から順にn個の座標点のゴミ(重量ci)を順番に拾い上げ、原点に戻ります.しかし、いつでも手のゴミは重さCを超えてはいけません.任意の2点距離はマンハッタン距離です.ロボットの歩く最も短い道のりを求めます.
Input
consists of multiple test cases. The first line of the input contains the number of test cases.There is a blank line before each dataset.The input for each dataset consists of a line containing one positive integer C, not greater then 100,indicating the maximum capacity of the robot, a line containing one positive integer N, not greaterthan 100,000, which is the number of packages to be loaded from the conveyer. Next, there are N linescontaining, for each package, two non-negative integers to indicate its delivery location in the grid, anda positive integer to indicate its weight. The weight of the packages is always smaller than the robotsmaximum load capacity. The order of the input is the order of appearance in the conveyer.
Output
For each test case, print one line containing one integer representing the minimum number of movesthe robot must travel to deliver all the packages.Print a blank line between datasets.
Sample Input
1
10 4
1 2 3
1 0 3
3 1 4
3 1 4
Sample Output
14
分析:
f[i]は、前のi個のゴミに必要な最大距離を示す.
dist[i]は、前のi個のゴミを拾う総距離である.
sumw[i]は重量の接頭辞和である.
origin[i]はi号ゴミから原点までの距離です.
f[i]では,j+1からiまでのごみを拾うことについて議論するが,方程式は容易ではない.
f[i]=min{f[j]+dist[i]-dist[j+1]+origin[i]+origin[j+1]} (sumw[i]-sum[j]<=maxw)
ゲージ時間の複雑さはO(n^2),maxn=10000000であり,TLEが明らかである.
方程式を研究するのは難しくない.
f[i]=dist[i]+origin[i]+ min{f[j]-dist[j+1]+origin[j+1]} (sumw[i]-sum[j]<=maxw)
value(j)=f[j]-dist[j+1]+origin[j+1]とする.
min{value[j]}は単調キュー前処理により得ることができ、ウィンドウモデルをスライドさせ、ウィンドウ制限:(sumw[i]-sum[j]<=maxw)
コードは次のとおりです.

#include<cstdio>
#include<iostream>
#include<cstdlib>
using namespace std;

const int maxn=100000+5;

int x[maxn],y[maxn];
int dist[maxn],origin[maxn],sumw[maxn];
int n,f[maxn],q[maxn],maxw;
inline void _read(int &x){
	char ch=getchar(); bool mark=false;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')mark=true;
	for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
	if(mark)x=-x;
}
void input(){
	int i,w; 
	_read(maxw);_read(n);
	for(int i=1;i<=n;i++){ 
		 _read(x[i]);_read(y[i]);_read(w);
		 //      
		 sumw[i]=sumw[i-1]+w;
		 origin[i]=x[i]+y[i];
		 dist[i]=dist[i-1]+abs(x[i]-x[i-1])+abs(y[i]-y[i-1]); 
	} 
}
int value(int x){  
	return f[x]-dist[x+1]+origin[x+1];
}
void solve(){
	int i,front,rear;
	f[0]=dist[0]=sumw[0]=0; 
	front=0;rear=1;  //     
	for(i=1;i<=n;i++){
		while(front!=rear&&sumw[i]-sumw[q[front]]>maxw)front++;
		f[i]=origin[i]+dist[i]+value(q[front]);
		while(front!=rear&&value(q[rear-1])>=value(i))rear--; //       
		q[rear++]=i;
	}
	printf("%d
",f[n]);
}
int main(){
	int t;
	_read(t);
	while(t--){
		input();
		solve();
		if(t>0)putchar('
');  //       
	} 
}

コンピュータ英語翻訳unit 7(3)

入門コマンド27-CMDウィンドウを終了する:exit