题目
输入 3 3 0 1 3 2 2 0 1 2 7 0 1 2 5 4 3 6 7 输出 3 2 9
题意：t组测试样例，下面两个数n，m；在下面是n个数，从中按顺序选不超过n个数满足这几个数的先加后减运算值最大.
思路：dp[i][0]表示这一个数应该进行的是减法，当然也可以对这个数不操作 dp[i][1]表示这一个数应该进行的是加法
AC code
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<sstream>
#include<stack>
#include<queue>
using namespace std
;
#define ll long long
ll n
,t
,m
,a
[360000],dp
[360000][2];
void solve()
{ ll i
,s
=0,ans
=0;
memset(dp
,0,sizeof(dp
));
for( i
=1;i
<=n
;i
++)
cin
>>a
[i
];
for(int i
=1;i
<=n
;i
++)
{
dp
[i
][0]=max(dp
[i
-1][0],dp
[i
-1][1]-a
[i
]);
dp
[i
][1]=max(dp
[i
-1][1],dp
[i
-1][0]+a
[i
]);
}
printf("%lld\n",max(dp
[n
][1],dp
[n
][0]));
}
int main()
{
ios
::sync_with_stdio(0);
cin
>>t
;
while(t
--)
{
cin
>>n
>>m
;
solve();}
}
