52 条题解
-
1
Sky1231 (sky1231) LV 10 @ 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); } -
1
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
readln(x,y);
readln(n);
for i:=1 to n do
readln(a[i],b[i]);
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.
``` -
0
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
struct your
{
int x,y;
}a[1010];
bool cmp(your j,your k)
{
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);
} -
0
Accepted_upc LV 8 @ 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;
}
``` -
0
/*
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;
} -
0
wang_yanheng LV 10 @ 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）。 -
0
我觉得这题目描述很坑爹啊,明明是坐标为[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;
} -
0
#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;
} -
0
wangshan0908 LV 10 @ 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
冒泡都过啊！ -
0
zhangyuchi45 LV 8 @ 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
Sky1231 (sky1231)
LV 10
@ 2017-03-11 11:29:50
