/ Vijos / 题库 / 飞翔 /

# 52 条题解

• @ 2017-03-11 11:29:50
``````#include <cmath>
#include <cstdio>
#include <algorithm>
#include <limits>
#define rt 1000
#define l 100
using namespace std;

int n,m,t,f[rt+1];

struct se_1
{
int x,y;
}a[rt+1];

bool cmp_se_1(se_1 x,se_1 y)
{
return (x.x<y.x||(x.x==y.x&&x.y<y.y));
}

int main()
{
scanf("%d%d%d",&n,&m,&t);
a[0].x=a[0].y=(numeric_limits<int>::max)();
for (int i=1;i<=t;i++)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+t+1,cmp_se_1);
double ans=(numeric_limits<double>::max)();
for (int i=1;i<=t;i++)
{
f[i]=1;
for (int j=1;j<i;j++)
if (a[j].x<a[i].x&&a[j].y<a[i].y)
f[i]=max(f[i],f[j]+1);
ans=min(ans,(double(n+m)*l)-(double(f[i])*(2-sqrt(2))*l));
}
printf("%.0lf",ans);
}
``````
• @ 2016-08-31 11:01:22

U41君前来刷题！！
```Pascal
var
x,y,n,i,max,j,maxn:longint;
a,b,f:array [0..1001] of longint;

procedure qsort(low,high:longint);
var i,j,mid,temp:longint;
begin
i:=low;j:=high;mid:=a[(i+j) div 2];
repeat
while a[i]<mid do i:=i+1;
while a[j]>mid do j:=j-1;
if i<=j then
begin
temp:=a[i];a[i]:=a[j];a[j]:=temp;
temp:=b[i];b[i]:=b[j];b[j]:=temp;
i:=i+1;j:=j-1;
end;
until i>j;
if i<high then qsort(i,high);
if j>low then qsort(low,j);
end;

begin
for i:=1 to n do
qsort(1,n);
f[1]:=0;
max:=0;
for i:=2 to n do
begin
maxn:=0;
for j:=1 to i-1 do
if (b[i]>b[j]) and (f[j]>maxn) then maxn:=f[j];
f[i]:=maxn+1;
if f[i]>max then max:=f[i];
end;
writeln(100*(x+y-(2-sqrt(2))*max):0:0);
end.
```

• @ 2016-09-19 12:51:31

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct your
{
int x,y;
}a[1010];
{
if(j.x==k.x)return j.y<k.y;

return j.x<k.x;
}
double nmp=sqrt(2);
int f[1010];
int tmp;
int m,n,z;
int main()
{
scanf("%d%d%d",&n,&m,&z);
for(int i=1;i<=z;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
}
sort(a+1,a+z+1,cmp);
f[1]=1;
for(int i=1;i<=z;i++)
{
for(int j=i;j>=1;j--)
{
if(a[i].x>a[j].x&&a[i].y>a[j].y&&f[i]<=f[j])
{
f[i]=f[j]+1;
}

}
if(f[i]==0){f[i]=1;}
if(f[i]>tmp){tmp=f[i];}

}
double ans=(m+n)*100-(2*tmp)*100+(tmp*nmp)*100;
printf("%.0lf",ans);
}

• @ 2016-09-16 22:35:15

之前明明过了9个点却返回全wa，全部AC才全部显示AC…………
```C++
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define maxn (1000 + 50)
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
using namespace std;
typedef long long int LLI;

struct Node {
int x;
int y;
} op[maxn];

bool cmp(Node a,Node b) {
return a.x < b.x;
}

double dp[maxn];

double Dis(Node a,Node b) {
return a.x - b.x - 1 + a.y - b.y - 1 + sqrt(2.0);
}

int main() {
// freopen("F:\乱七八糟的东西\ACM相关\数据\vijos数据\P1336\Input\input4.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i = 1; i <= k; i ++) {
scanf("%d%d",&op[i].x,&op[i].y);
}
sort(op + 1,op + k + 1,cmp);
for(int i = 1; i <= k; i ++) {
dp[i] = op[i].x + op[i].y - 2;
}
for(int i = 1; i <= k; i ++) {
for(int j = 1; j < i; j ++) {
if(op[i].x > op[j].x && op[i].y > op[j].y) {
dp[i] = min(dp[j] + Dis(op[i],op[j]),dp[i]);
}
}
}
double re = n + m ;
for(int i = 1; i <= k; i ++) {
re = min(re,dp[i] + n - op[i].x + m - op[i].y + sqrt(2.0));
}
printf("%.0lf\n",re * 100);
return 0;
}
```

• @ 2016-08-10 08:07:43

/*
LIS问题，坐标递增关系递推即可，注意应排序，且排序后横纵坐标双重条件不能少
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <cstdlib>
using namespace std;

struct node
{
int x,y;
}a[100002];
int n,m,k;
int f[100002];

int cmp(node a,node b)
{
return a.x<b.x;
}

int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
sort(a+1,a+k+1,cmp);//一定要排序~
int ans=-9;
for(int i=0;i<=k;i++)
f[i]=1;
for(int i=1;i<=k;i++)
{
for(int j=1;j<=k;j++)
if(a[i].x>a[j].x&&a[i].y>a[j].y)//双重条件不能少
f[i]=max(f[j]+1,f[i]);
ans=max(ans,f[i]);
}

cout<<int(100*(double(n+m-2*ans)+sqrt(2)*ans)+0.5)<<endl;
return 0;
}

• @ 2014-11-29 22:22:09

#include <stdio.h>
#include <math.h>
struct way{
int x,y,period,sum;
};
struct way arr[1000];
struct way temp;
void quickSort(int left,int right){
int l=left,r=right;
int mid=arr[(left+right)/2].period;
while(l<=r){
while(arr[l].period<mid)
l++;
while(arr[r].period>mid)
r--;
if(l<=r){
temp=arr[l];
arr[l]=arr[r];
arr[r]=temp;
l++,r--;
}
}
if(left<r)
quickSort(left,r);
if(l<right)
quickSort(l,right);
}
int main(){
int row,column,num;
int i,k;
scanf("%d%d%d",&column,&row,&num);
for(i=0;i<num;i++){
scanf("%d%d",&arr[i].x,&arr[i].y);
arr[i].period=arr[i].x+arr[i].y;
arr[i].sum=1;
}
quickSort(0,num-1);
for(i=0;i<num;i++){
for(k=0;k<i;k++){
if(arr[k].x<arr[i].x && arr[k].y<arr[i].y){
if(arr[k].sum+1>arr[i].sum)
arr[i].sum=arr[k].sum+1;
}
}
}
k=0;
for(i=0;i<num;i++){
if(arr[i].sum>k)
k=arr[i].sum;
}
printf("%.0lf\n",100*(row+column-2*k)+100*sqrt(2)*k);
return 0;
}

大概说一下思路：
题目需要求最短路径，等价于求最多能走多少斜边。而对于任意一条斜边，最优解等于其左下范围内的最优解+1。排序做的事其实是分出阶段，以便从左下角一直搜到右上角。DP完后，找到最大值k。显然，假设一条斜边也不走，那么就要走（长+宽）条直边，每多走一条斜边则少走两条直边，因此走的直边数为（长+宽-2*k）。

• @ 2014-10-08 21:38:19

yy了一下，然后觉得这题有点麻烦，可能要离散化+bit维护区间最值，然后看了下k发现很小，而n,m范围又不大就懒得用离散化，就直接用bit……

• @ 2013-11-03 16:48:42

这是一道包装的很好的LIS。。。

• @ 2013-05-25 15:44:15

我觉得这题目描述很坑爹啊,明明是坐标为[M,N]边的个数应该是M-1,N-1啊,结果狂试一番......
#include <iostream>
using namespace std;
int x[1100], y[1100], F[1100];
int main()
{
const double s2 = 141.4213;
int m, n, k;
cin >> n >> m >> k;
for (int i = 0; i < k; i++)
cin >> x[i] >> y[i];

for (int i = 0; i < k; i++)
{
for (int j = i + 1; j < k; j++)
{
if (x[i] > x[j])
{
swap (x[i], x[j]);
swap (y[i], y[j]);
}
}
}

for (int i = 0; i < k; i++)
{
for (int j = 0; x[j] < x[i]; j++)
{
if (F[j] > F[i] && y[j] < y[i]) F[i] = F[j];
}
F[i]++;
}

int max(0);
for (int i = 0; i < k; i++) if (F[i] > max) max = F[i];

double l = double(max) * s2 + 100 *(n + m - 2 * max);
max = l + 0.5000;
cout << max;

return 0;
}

• @ 2013-05-25 15:24:26

#include <iostream>
#include <math.h>
using namespace std;
int F[1000][1000],X[1000],Y[1000];
int main()
{
int m,n,k,i,j,l;
cin>>m>>n>>k;
for(i=0;i<k;i++) cin>>X[i]>>Y[i];
for(i=0;i<1000;i++)
for(j=0;j<1000;j++)
for(l=0;l<k;l++)
{
while(i!=X[l],j!=Y[l])
{
F[X[i]][Y[i]]=min(F[X[i]-1][Y[i]],F[X[i]][Y[i]-1]);
}
F[X[i]][Y[i]]=F[X[i]-1][Y[i]-1]+sqrt(2);
}
cout<<F[m][n]<<endl;
return 0;
}

• @ 2012-10-18 21:43:05

为啥DP会非法存取啊

• @ 2009-11-09 21:24:24

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：运行超时|无输出...

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

90分，但显示的状态却是AC,我无语

• @ 2009-11-09 16:02:06

无语，忘记把调试输出的部分删掉...

• @ 2009-11-03 22:02:16

在四舍五入上闹了好久，结果竟然是2^1/2的精度不够，郁闷

1.414是不行的

• @ 2009-10-25 16:38:13

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

冒泡都过啊！

• @ 2009-10-25 12:27:10

200题纪念！

• @ 2009-08-30 14:31:03

快排+DP为什么会存取非法

• @ 2009-08-25 12:15:20

nlogn,水题

• @ 2009-08-20 16:55:26

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

按照x+y快排,搞O(n^2)的最长不下降子序列(p[i].x>p[j].x && p[i].y>p[j].y),最后用double的路程就可以了。

s=100*n+100*m-max*a;

cout

• @ 2009-03-16 16:05:06

看了题解才知道原来是最长上升子序列啊~

快排+DP就过了

ID
1336

5

(无)

1379

436

32%

4