首页 > 代码库 > CSU 1225 最长上升子序列并记录其个数
CSU 1225 最长上升子序列并记录其个数
1 for(int j=0;j<i;j++){ 2 if(h[i] > h[j]){ 3 if(len[i] == len[j] + 1) cnt[i]+=cnt[j]; 4 if(len[i] < len[j] + 1) len[i] = len[j] + 1 , cnt[i] = cnt[j]; 5 } 6 //身高相同的情况统计 7 /*else if(h[i] == h[j]){ 8 if(len[i] == len[j]) cnt[i] += cnt[j]; 9 if(len[i] < len[j]) len[i] = len[j] , cnt[i] = cnt[j];10 }*/11 }
这道题需要注意的一点是如果出现身高相同的情况，那么这两个人不管谁站在队列中只算一种情况：如上面的代码所示，如果相同也统计那么就会报错，但是样例因为没有相同高度所以可以过
len[i] 表示前i个对象能构建的最长的子序列长度
cnt[i] 表示前i个对象构建的最长子序列长度的个数
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 #define max(a,b) a>b?a:b 5 const int N = 1005; 6 int h[N] , len[N] , cnt[N]; 7 int main() 8 { 9 freopen("test.in","rb",stdin);10 int n;11 while(scanf("%d",&n)!=EOF){12 memset(len , 0 ,sizeof(len));13 memset(cnt , 0 ,sizeof(cnt));14 len[0] = 1 , cnt[0] = 1;15 for(int i = 0;i < n;i++)16 {17 len[i] = cnt[i] = 1;18 scanf("%d",h+i);19 for(int j=0;j<i;j++){20 if(h[i] > h[j]){21 if(len[i] == len[j] + 1) cnt[i]+=cnt[j];22 if(len[i] < len[j] + 1) len[i] = len[j] + 1 , cnt[i] = cnt[j];23 }24 /*else if(h[i] == h[j]){25 if(len[i] == len[j]) cnt[i] += cnt[j];26 if(len[i] < len[j]) len[i] = len[j] , cnt[i] = cnt[j];27 }*/28 }29 }30 int max_len = 0 , cnt_all = 0;31 for(int i=0;i<n;i++){32 max_len = max(max_len , len[i]);33 }34 for(int i=0;i<n;i++){35 if(max_len == len[i])36 cnt_all += cnt[i];37 }38 printf("%d %d\n",max_len,cnt_all);39 }40 return 0;41 }
CSU 1225 最长上升子序列并记录其个数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。