C++分析研究  
C++
日历
<2013年6月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456
统计
  • 随笔 - 92
  • 文章 - 4
  • 评论 - 4
  • 引用 - 0

导航

常用链接

留言簿

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 

题目的大概意思:有一系列老鼠,每个老鼠有体重w以及奔跑的速度s,求这样一个最大的序列,使得托福答案
m[i+1].w > m[i].w && m[i+1].s < m[i].s
一开始,我用"DAG上的动态规划"来解决这道题目,把每一个老鼠看成是有向图中的一个顶点,有向边(v1, v2)存在的充要条件是m[v2].w > m[v1].w && m[v2].s < m[v1].s
那题目就转换为求一个DAG中不确定起点的最长路径,用记忆化搜索DP轻松KO,但是我就不知道为啥不能AC(算法复杂度太高?),如果你知道,告诉我,不胜感激
d[i]表示以i为起点的最长路径
dp(i, n)//求解以i为起点的最长路径
最后,最长路径 = max {dp(i, n)}
[html]
#include <iostream>
using namespace std;
struct Mouse{
int w, s;
Mouse(int _w, int _s): w(_w), s(_s) {}
Mouse(){}
};
Mouse mouse[1001];
int G[1001][1001];
int d[1001];
int dp(int i, int n) {
int& ans = d[i];
if (ans > 0) return ans;
ans = 1;
for (int j = 1; j <= n; j++)
if (G[i][j]) {
int tmp = dp(j, n) + 1;
if (ans < tmp) {
ans = tmp;
}
}
return ans;
}
void print_path(int i, int n) {
cout 《 i 《 endl;
for (int j = 1; j <= n; ++j)
if (G[i][j] && d[i] == d[j] + 1) {
print_path(j, n);
break;
}
}
int main() {
int w,s,n = 0;
memset(d, -1, sizeof(d));
while (scanf("%d%d", &w, &s) != EOF)
mouse[++n] = Mouse(w, s);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j)
if (mouse[j].w > mouse[i].w && mouse[j].s < mouse[i].s)
G[i][j] = 1;
else
G[i][j] = 0;
}
int MAX = 0;
int ans;
for (int i = 1; i <= n; i++)
if (MAX < dp(i, n)) {
MAX = d[i];
ans = i;
}
cout 《 ans 《 endl;
print_path(ans, n);
return 0;
}

其实一开始我想到的不是DAG,而是将所有老鼠按体重排序,并且体重相同的可以按照速度逆序排,这样,题目就转换为求解最大递减子序列,用dp[i]表示以第i个老鼠(排过序之后)为起点的最大递增子序列,状态转移方程为
dp[i] = max {dp[j]}+1 && (m[j].w > m[i].w && m[j].s < m[i].s 表示j可以接在j前面 ) j = i+1, … n
最后,放出AC代码
[html]
#include <iostream>
using namespace std;
struct Mouse{
int w, s, id, next;
Mouse(int _w, int _s): w(_w), s(_s), next(-1) {}
Mouse(){}
};
Mouse m[1001];
int dp[1001];
int cmp(const void *a, const void *b) {
if (((Mouse*)a)->w == ((Mouse*)b)->w)
return ((Mouse*)b)->s - ((Mouse*)a)->s;
else
return ((Mouse*)a)->w - ((Mouse*)b)->w;
}
int main() {
int w, s, n = 1;
while (cin 》 m[n].w 》 m[n].s)
m[n].id = n++;
--n;
qsort(m+1, n, sizeof(m[1]), cmp);
int max = 0;
int flag;
for (int i = n; i >= 1; --i) {
dp[i] = 1;
for (int j = i + 1; j <= n; ++j) {
if (m[j].w > m[i].w && m[j].s < m[i].s)
if (dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
m[i].next = j;
}
}
if (max < dp[i]) {
max = dp[i];
flag = i;
// dp[i]表示以i开头的最大长度
}
}
cout 《 max 《 endl;
for (int i = 1; i <= max; ++i) {
cout 《 m[flag].id 《 endl;
flag = m[flag].next;
}
return 0;
}
 

posted on 2013-06-25 20:28 HAOSOLA 阅读(268) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


 
Copyright © HAOSOLA Powered by: 博客园 模板提供:沪江博客
PK10开奖 PK10开奖