BestCoder Round #91 1001 Lotus and Characters

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6011

题意：

Lotus有nn种字母，给出每种字母的价值以及每种字母的个数限制，她想构造一个任意长度的串。 定义串的价值为：第1位字母的价值*1+第2位字母的价值*2+第3位字母的价值*3…… 求Lotus能构造出的串的最大价值。（可以构造空串，因此答案肯定\geq 0≥0）

分析：

做这个题目的时候，第一感觉回溯算了，不用想，肯定T了。

1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int n; 6 int val[30]; 7 int cnt[30]; 8 int len; 9 10 int dfs(int cur) 11 { 12 int ans = 0; 13 if(cur>=len+1) return 0; 14 else 15 { 16 for(int i=0; i<n; i++) 17 { 18 if(cnt[i]>0) 19 { 20 cnt[i]--; 21 ans = max(ans,(cur+1)*val[i]+dfs(cur+1)); 22 cnt[i]++; 23 } 24 } 25 } 26 return ans; 27 } 28 29 int main() 30 { 31 int t; 32 scanf("%d",&t); 33 34 while(t--) 35 { 36 scanf("%d",&n); 37 len = 0; 38 for(int i=0; i<n; i++) 39 { 40 scanf("%d%d",&val[i],&cnt[i]); 41 len+=cnt[i]; 42 } 43 44 printf("%d\n",dfs(0)); 45 } 46 return 0; 47 }

 

后来想DP，直觉告诉我，正权值的放后面。每次计算后面的数值，又不知道前面有多少位，怎么解决这个问题呢？

就类似于前缀和，写一个后缀和，之前的位数不确定，怎么解决呢？

Ans[i] = Ans[i+1] + sum[i+1] +v[i];

状态转移就是多加了一遍后缀和，和首位。最后找一下最好的切割点。

其实这个切割点也可以从后往前找。

1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int main() 6 { 7 int t; 8 scanf("%d",&t); 9 while(t--) { 10 int n; 11 scanf("%d",&n); 12 13 vector<int> v; 14 15 for(int i=0;i<n;i++) { 16 int val,cnt; 17 scanf("%d%d",&val,&cnt); 18 for(int i=0;i<cnt;i++) { 19 v.push_back(val); 20 } 21 } 22 23 sort(v.begin(),v.end()); 24 25 int len = v.size(); 26 27 int Ans[10010]; 28 int sum[10010]; 29 30 memset(Ans,0,sizeof(Ans)); 31 memset(sum,0,sizeof(sum)); 32 33 for(int i=len-1;i>=0;i--) { 34 sum[i] = sum[i+1] + v[i]; 35 } 36 37 for(int i=len-1;i>=0;i--) { 38 Ans[i] = Ans[i+1] + sum[i+1] + v[i]; 39 } 40 41 int ans = 0; 42 43 //for(int i=0;i<len;i++) { 44 // ans = max(ans,Ans[i]); 45 //} 46 47 48 for(int i=len-1;i>=0;i--) { 49 if(ans<Ans[i]) 50 ans = Ans[i]; 51 else break; 52 } 53 54 printf("%d\n",ans); 55 } 56 57 return 0; 58 }

 

转载于:https://www.cnblogs.com/TreeDream/p/6339982.html

总结

以上是生活随笔为你收集整理的BestCoder Round #91 1001 Lotus and Characters的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。