https://www.nowcoder.com/acm/contest/79#question
说是比赛题解，其实我只会前三题；
后面的一定补
T1
题意，在一个长度为n的时间内，问如何选择存款期限，使得收益最大。
dp
#include#include #include #include using namespace std;#define fi first#define se seconddouble r[5];double dp[30];double ll(int n,int id,double a){ double t=1.0; for(int i=1;i<=n;i++) { t=t*(1+r[id]); } return t*a;}int main(){ int n; scanf("%d%lf%lf%lf%lf",&n,&r[1],&r[2],&r[3],&r[4]); memset(dp,0,sizeof(dp)); dp[0]=1.0; for(int i=1;i<=n;i++) { for(int j=1;j<=4;j++) { int nian=(j==4)?5:j; if(i>=nian) { dp[i]=max(ll(nian,j,dp[i-nian]),dp[i]); } } } printf("%.5lf\n",dp[n]); return 0;}
T2
利用前缀和即可；
#include#include #include #include #include typedef long long ll;using namespace std;const int maxn = 1000009;ll a[maxn],b[maxn];ll n,m;bool cmp(ll a,ll b){ return a > b;}int main(){ scanf("%lld%lld",&n,&m); for(int i=1; i<=n; i++) { scanf("%lld",&a[i]); } for(int i=1;i<=n;i++) { scanf("%lld",&b[i]); } a[0]=0,b[0]=0; sort(a+1,a+1+n); sort(b+1,b+1+n,cmp); for(int i=1;i<=n;i++) { a[i]+=a[i-1]; b[i]+=b[i-1]; } ll ans = 0; ll ff=0; for(int i=1;i<=n; i++) { if(i%3==0) ff+=m; ll tmp = b[i]-a[i]+ff; if(tmp>ans)ans=tmp; } printf("%lld\n",ans); return 0;}
T3
题意：操作一个只含a，b的字符串，问能最少删去字母个数，使得在最后的字符串中，相邻不同的个数少于m个；
思路：dp；这题关键就是把（且新的字符串的首字母必须是'a'）这句话发挥得淋漓尽致，这也规定了答案字符串中，必须是一块a，一块b，一块a……
所以，如果 j 是偶数，表示后面就要接a，如果 j 是奇数，必须要有b才行；
#include#include #include #include #include #include #define pb push_backtypedef long long ll;using namespace std;const int maxn = 1000009;ll dp[maxn][20];string s1;int n,m;int main(){ cin>>n>>m>>s1; s1="*"+s1; memset(dp,0,sizeof(dp)); int flag=1; for(int i=1; i<=n; i++) { for(int j=0; j<=m; j++) { dp[i][j]=max(dp[i][j],dp[i-1][j]); } for(int j=0; j<=m; j++) { if(((j&1)&&s1[i]=='b')||(((j&1)==0)&&s1[i]=='a')) { if(j!=0)dp[i][j]=max(dp[i][j], dp[i-1][j-1]+1); dp[i][j]=max(dp[i][j], dp[i-1][j]+1); } } if(s1[i]=='a')flag=0; //最后尽然把全b的情况忘记了 } ll ans = 0; for(int i=0; i<=m; i++) { ans=max(ans, dp[n][i]); } if(flag)cout<<0<