公厂做网站需要开诚信通吗,古云网站建设,排名好的宜昌网站建设,wordpress登不进后台题目链接#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid6011 题意#xff1a; Lotus有nn种字母#xff0c;给出每种字母的价值以及每种字母的个数限制#xff0c;她想构造一个任意长度的串。 定义串的价值为#xff1a;第1位字母的价值*1第2位字母的价值*2第3位字…题目链接http://acm.hdu.edu.cn/showproblem.php?pid6011 题意 Lotus有nn种字母给出每种字母的价值以及每种字母的个数限制她想构造一个任意长度的串。 定义串的价值为第1位字母的价值*1第2位字母的价值*2第3位字母的价值*3…… 求Lotus能构造出的串的最大价值。可以构造空串因此答案肯定\geq 0≥0 分析 做这个题目的时候第一感觉回溯算了不用想肯定T了。 1 #include bits/stdc.h2 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(curlen1) return 0;
14 else
15 {
16 for(int i0; in; i)
17 {
18 if(cnt[i]0)
19 {
20 cnt[i]--;
21 ans max(ans,(cur1)*val[i]dfs(cur1));
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 i0; in; i)
39 {
40 scanf(%d%d,val[i],cnt[i]);
41 lencnt[i];
42 }
43
44 printf(%d\n,dfs(0));
45 }
46 return 0;
47 } 后来想DP直觉告诉我正权值的放后面。每次计算后面的数值又不知道前面有多少位怎么解决这个问题呢 就类似于前缀和写一个后缀和之前的位数不确定怎么解决呢 Ans[i] Ans[i1] sum[i1] v[i]; 状态转移就是多加了一遍后缀和和首位。最后找一下最好的切割点。 其实这个切割点也可以从后往前找。 1 #include bits/stdc.h2 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 vectorint v;
14
15 for(int i0;in;i) {
16 int val,cnt;
17 scanf(%d%d,val,cnt);
18 for(int i0;icnt;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 ilen-1;i0;i--) {
34 sum[i] sum[i1] v[i];
35 }
36
37 for(int ilen-1;i0;i--) {
38 Ans[i] Ans[i1] sum[i1] v[i];
39 }
40
41 int ans 0;
42
43 //for(int i0;ilen;i) {
44 // ans max(ans,Ans[i]);
45 //}
46
47
48 for(int ilen-1;i0;i--) {
49 if(ansAns[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
