首页 > 代码库 > hdu 5914 Triangle
hdu 5914 Triangle
题意:1 2 ....n,这些边中最少抽出多少条边,使得剩下的边无法组成三角形
分析:开始的时候有点zz,IDA*跑了一发,2^(n-2)*n^3,跑了5min出了17,剩下的怎么都出不来了,然后YY了一下n和ans[n]之间的差,就过了,后来想了一下使得剩下的边都不能组成三角形,只要剩下的都是Fibonacci序列中的数就行了,想想IDA*简直就s是zz啊
#include<bits/stdc++.h>using namespace std;int dp[25];int main(){ dp[1]=dp[2]=dp[3]=dp[5]=dp[8]=dp[13]=dp[21]=1; for(int i=2;i<=20;i++)dp[i]+=dp[i-1]; int t,n,cas=1; cin>>t; while(t--){ cin>>n; printf("Case #%d: %d\n",cas++,n-dp[n]); } return 0;}
hdu 5914 Triangle
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。