UVA-10131

题意:

       输入一些大象的的重量和智商,找出满足:按重量严格递增,智商严格递减(严格递减的意思就是只能小于,不能等于)的最长的序列。

解法:

      参照小白书上的方法,将问题转换为求DAG上的最长路径问题(此题显然不存在自环、闭环以及重复边,因此可以转换为DAG问题)。

      DAG使用邻接矩阵G存放,G[i][j] = true表示第i头大象重量大于第j头大象,且第i头大象智商小于第j头大象。

     注意此题的最长路径是不固定起点和终点的,这里用的是记忆化DP(dijkstra等算法当然也能行得通)。使用DP[i]表示从i出发的最长路径,状态转移方程简单来讲就是:

从i出发的最长路径 = 所有i的邻居中最长路径 + 1。 

即 DP[i] = max(DP[j] + 1), G[i][j] == true。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
bool G[1001][1001];
int DP[10010], n;
int dp(int i)
{
if (DP[i] > 0) return DP[i];
int k = 1;
for (int j = 1; j <= n; j++) if(G[i][j])
k = max(k,1 + dp(j));
return DP[i] = k;
}
void printg(int i)
{
cout << i << endl;
for (int j = 1; j <= n; j++) if (G[i][j]&&DP[j] + 1 == DP[i])
{
printg(j); break;
}
}
int main()
{
int a[1001][2], mi = 0;
memset(G, 0, sizeof(G)); memset(DP, 0, sizeof(DP));
for (n = 1; cin >> a[n][0] >> a[n][1]; n++);
for (int i = 1; i <= n; i++) for (int j = i + 1; j <= n; j++)
{
G[i][j] = (a[i][0]<a[j][0] && a[i][1]>a[j][1]) ? true : false;
G[j][i] = (a[j][0]<a[i][0] && a[j][1]>a[i][1]) ? true : false;
}
for (int i = 1; i <= n; i++)
if (dp(i) > DP[mi]) mi = i;
cout << DP[mi] << endl; printg(mi);
return 0;
}

 

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

UVA-10131

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » UVA-10131
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏