简答题 偏难
#22111

上升点列(point)

上升点列(point)


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include&lt;bits/stdc++.h&gt; using namespace std; struct node{ int x,y; //重载运算符,按x从小到大排序,x相同,则按y从小到大排序 friend bool operator&lt;(const node &amp;a1,const node &amp;a2){ if(a1.x!=a2.x)return a1.x&lt;a2.x; return a1.y&lt;a2.y; } }a[505];//记录500个点 int f[505][105],n,m,ans; int main(){ cin&gt;&gt;n&gt;&gt;m; for(int i=1;i&lt;=n;i++)cin&gt;&gt;a[i].x&gt;&gt;a[i].y; sort(a+1,a+1+n);//排序 for(int k=0;k&lt;=m;k++){//枚举使用0到K个点的情况 for(int i=1;i&lt;=n;i++){//枚举每一个点 f[i][k]=k+1;//初始化第i个点用掉K个添加点后的最长距离 for(int j=1;j&lt;i;j++){//循环这个点之前的点 if(a[j].y&gt;a[i].y)continue;//如果之前的点Y坐标大,则忽略 int dist=a[i].x-a[j].x+a[i].y-a[j].y;//计算距离 if(dist-1&gt;k)continue;//如果距离大,添加的点不够用,则忽略 f[i][k]=max(f[i][k],f[j][k-dist+1]+dist);//看下现在的大还是换成之前的点大 } ans=max(ans,f[i][k]+m-k);//跟最大值比较 } } cout&lt;&lt;ans; return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include&lt;bits/stdc++.h&gt;  using namespace std; int n,k; struct points {     int x,y; } p[510];   bool cmp(const points a,const points b)  {     if(a.x==b.x) return a.y&lt;b.y;     else return a.x&lt;b.x; } int f[510][110];//以i点为终点,再添加上j个点的情况下最大序列长度 int main()  { //打开输入文件,输出文件 freopen("point.in","r",stdin); freopen("point.out","w",stdout);     scanf("%d %d",&amp;n,&amp;k);     for(int i=1; i&lt;=n; i++)  {         scanf("%d %d",&amp;p[i].x,&amp;p[i].y);     }     sort(p+1,p+1+n,cmp);     int ans=0;     for(int i=1; i&lt;=n; i++)  {//以i为终点         for(int j=0; j&lt;=k; j++)  {//添加j个点             f[i][j]=j+1;//以i为终点,后续添加j个点最短的长度             for(int l=1; l&lt;i; l++)  { //l为i的前一个点                 if(p[l].x&lt;=p[i].x&amp;&amp;p[l].y&lt;=p[i].y)  {//横坐标、纵坐标值均单调不减                     int t=p[i].x-p[l].x+p[i].y-p[l].y-1;//需要添加的点数量                     if(j&gt;=t) f[i][j]=max(f[i][j],f[l][j-t]+t+1);                     //cout&lt;&lt;p[i].x&lt;&lt;p[l].x&lt;&lt;p[i].y&lt;&lt;p[l].y&lt;&lt;t&lt;&lt;endl;                 }                 //cout&lt;&lt;"i="&lt;&lt;i&lt;&lt;" j="&lt;&lt;j&lt;&lt;" l="&lt;&lt;l&lt;&lt;" f="&lt;&lt;f[i][j]&lt;&lt;endl;             }               ans=max(ans,f[i][j]);         }     }     printf("%d",ans);     //关闭输入文件输出文件 fclose(stdin); fclose(stdout);     return 0; }</pre><p><br/></p>
这道题暂未补解析。