题目描述 Description
大妈打完三战回家，我知道他是怎么回来的，欧洲到日本有L个站点他决定乘坐恰好n次飞机（不是学院都市的超音速飞机）和m次火车来从第一个站点到达最后一个站点。但是有一点很重要的就是跟御坂美琴那样的壕不同大妈很穷，所以他决定要尽量花费最少的费用，当然如果能赚到钱那就更好了。由于当麻交友甚广，他们在某些站点可以见到一些故友，可以得到资助，而在有些站点不但不会赚钱，还会因为要住宿，买车票，旅游等而花费一定的费用。如果他乘坐火车，那么就会受到所经过的站点（包括终点不包括起点）的影响，花费一定费用或赚到一定的钱，而他做飞机的话就不会受到站点的影响，他已经知道了每个站点的情况，为防止钱花的过多被index咬头他决定找你来帮他找到最省钱（赚钱）的方案
输入描述 Input Description
输入文件back.in第一行包含三个整数，为他们决定坐火车的次数m，他们决定坐飞机的次数n，站点数L。第二行为L个整数，每个数都在-200到200之间，表示每个站点的情况，正数表示能赚到钱，负数表示会花费钱。
输出描述 Output Description
输出文件back.out包含一个整数，表示他们最多能赚到多少钱（如果入不敷出就输出负数来表示他们花了多少钱）。
样例输入 Sample Input
6 6 14
12 32 43 -1 32 -9 -10 32 -43 -21 -32 12 -31 -3
样例输出 Sample Output
150
数据范围及提示 Data Size & Hint
【样例解释】
一种最赚钱的方法为：1-〉2（火车），2-〉3（火车），3-〉4（火车），4-〉5（火车），5-〉7（飞机），7-〉8（火车），8-〉9（飞机），9-〉10（飞机），10-〉11（飞机），11-〉12（火车），12-〉13（飞机），13-〉14（飞机）
【数据范围】
n+m<L
对于60%的数据，1<=n，m<=50，1<=L<=200。
对于100%的数据，1<=n，m<=200，1<=L<=500。
/* DP方程式很好想的，设f[i][j][k]为用了i次火车，j次飞机，走到k点的最大收益。 转移：f[i][j][k]=max(f[i-1][j][pos]+s[k]-s[pos],f[i][j-1][pos]) 但是这样时间和空间都会超，空间数组滚一下，至于时间，我们发现每次更新f[i][j][…]的都是f[i-1][j][…]， 所以可以考虑维护一个最大值。 */ #include<cstdio> #include<iostream> #include<cstring> #define N 210 #define M 60 using namespace std; int a[N],s[N],f[2][M][N],n,c1,c2,mx1[2][M][N],mx2[2][M][N]; int main(){ memset(f,-127/3,sizeof(f)); memset(mx1,-127/3,sizeof(mx1)); memset(mx2,-127/3,sizeof(mx2)); scanf("%d%d%d",&c1,&c2,&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); s[i]=s[i-1]+a[i]; } f[0][0][1]=mx1[0][0][1]=mx2[0][0][1]=0; for(int i=0;i<=c1;i++){ for(int j=0;j<=c2;j++){ for(int k=1;k<=n;k++){ if(i)f[i&1][j][k]=max(f[i&1][j][k],mx1[(i+1)&1][j][k-1]+s[k]); if(j)f[i&1][j][k]=max(f[i&1][j][k],mx2[i&1][j-1][k-1]); } for(int k=1;k<=n;k++){ mx1[i&1][j][k]=max(mx1[i&1][j][k-1],f[i&1][j][k]-s[k]); mx2[i&1][j][k]=max(mx2[i&1][j][k-1],f[i&1][j][k]); } } for(int j=0;j<=c2;j++) for(int k=1;k<=n;k++){ f[i+1&1][j][k]=-100000000; mx1[i+1&1][j][k]=-100000000; mx2[i+1&1][j][k]=-100000000; } } printf("%d ",f[c1&1][c2][n]); return 0; }