BestCoder——59
http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=640
第一题:给一堆书的序列 每次操作只能将书从中间移到最上面 求最少移动多少次 使得有序
只有19本书
怎么暴力怎么来
可以观察出 一本书最多被移动一次 不然移动就不存在意义了
ID最大的书是不被移动的 so 倒着查询有多少本是不被移动的就行了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 5 using namespace std; 6 7 8 int a[50]; 9 int main() 10 { 11 int Cas; 12 scanf("%d",&Cas); 13 while (Cas--) 14 { 15 int n; 16 scanf("%d",&n); 17 for (int i = 1;i<=n;i++) 18 scanf("%d",&a[i]); 19 for (int i = n;i>=1;i--) 20 { 21 if (a[i] == n) 22 n--; 23 } 24 printf("%d ",n); 25 } 26 return 0; 27 }
第二题:求最多的分数
sum = a[i] - b[i]*(耗费的时间)
贪心 加 搜索
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 7 typedef long long LL; 8 const int maxn = 10000 + 100; 9 struct node{ 10 int a,b,c; 11 }p[maxn]; 12 13 bool cmp(node t1,node t2) 14 { 15 return (LL)t1.c*t2.b < (LL)t2.c*t1.b; 16 } 17 int dp[maxn]; 18 int main() 19 { 20 int Cas; 21 scanf("%d",&Cas); 22 while (Cas--) 23 { 24 int n,t; 25 scanf("%d%d",&n,&t); 26 for (int i = 1;i<=n;i++) 27 { 28 scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c); 29 30 } 31 sort(p+1,p+n+1,cmp); 32 33 34 memset(dp,0,sizeof(dp)); 35 for (int i = 1;i<=n;i++) 36 { 37 for (int j = t;j>=p[i].c;j--) 38 { 39 dp[j] = max(dp[j],dp[j-p[i].c] + (p[i].a - p[i].b * j)); 40 } 41 } 42 int ans = 0; 43 for(int i = 0; i <= t; i++) ans = max(ans, dp[i]); 44 printf("%d ", ans); 45 46 } 47 return 0; 48 }