链接：https://www.nowcoder.com/acm/contest/140/D
来源：牛客网
The first line contains an integer T(0<T<=5), denoting the number of test cases.
In each test case, there is one integer n(0<n<=100000) in the first line,denoting the number of stores.
For the next line, There are n integers in range [0,2147483648), denoting a[1..n].
For each test case, print a single line containing 2 integers, denoting the maximum profit and the minimum number of transactions.
3 4
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<math.h> #include<algorithm> #define MAX 100005 #define INF 0x3f3f3f3f #define MOD 1000000007 using namespace std; typedef long long ll; int a[MAX],dpg[MAX][2]; ll dpf[MAX][2]; int main() { int t,n,i,j; scanf("%d",&t); while(t--){ scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&a[i]); } memset(dpf,0,sizeof(dpf)); memset(dpg,0,sizeof(dpg)); dpf[1][0]=0; dpf[1][1]=-a[1]; dpg[1][0]=0; dpg[1][1]=1; for(i=2;i<=n;i++){ if(dpf[i-1][0]>=dpf[i-1][1]+a[i]){ dpf[i][0]=dpf[i-1][0]; dpg[i][0]=dpg[i-1][0]; } else{ dpf[i][0]=dpf[i-1][1]+a[i]; dpg[i][0]=dpg[i-1][1]+1; } if(dpf[i-1][0]-a[i]>dpf[i-1][1]){ dpf[i][1]=dpf[i-1][0]-a[i]; dpg[i][1]=dpg[i-1][0]+1; } else{ dpf[i][1]=dpf[i-1][1]; dpg[i][1]=dpg[i-1][1]; } } printf("%lld %d\n",dpf[n][0],dpg[n][0]); } return 0; }
原文：https://www.cnblogs.com/yzm10/p/9362700.html