简单贪心。
因为填的字母没有次数限制,所以最优策略很容易想到,就是在最后面填最大的。
不用实际去填,算出ans就可以。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <iostream> #include <cmath> #include <cstring> #include <algorithm> using namespace std; int main() { int k,len; char st[2000]; int a[2000]; memset(a,0,sizeof(a)); int w[50]; cin>>st>>k; int m=-1; for (int i=1;i<=26;i++) { cin>>w[i]; if (w[i]>m) m=w[i]; } len=strlen(st); for (int i=0;i<len;i++) a[i]=(int)(st[i]-96); long long ans=0; for (int i=0;i<len;i++) { ans=ans+w[a[i]]*(i+1); // cout<<ans<<endl; } for (int i=len;i<len+k;i++) ans=ans+m*(i+1); cout<<ans<<endl; return 0; } |
说点什么
您将是第一位评论人!