/ Vijos / 题库 / 飞翔 /

题解

52 条题解

  • 1
    @ 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
    @ 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
    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
    @ 2016-09-19 12:51:31

    #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
    @ 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
    @ 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;
    }

  • 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)。

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

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

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

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

  • 0
    @ 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;
    }

  • 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;
    }

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

    为啥DP会非法存取啊

  • 0
    @ 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,我无语

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

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

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

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

    1.414是不行的

  • 0
    @ 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
    @ 2009-10-25 12:27:10

    200题纪念!

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

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

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

    nlogn,水题

  • 0
    @ 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

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

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

    快排+DP就过了

信息

ID
1336
难度
5
分类
动态规划 | 单调性DP 点击显示
标签
(无)
递交数
1386
已通过
438
通过率
32%
被复制
4
上传者