poj 1722 线性DP好题_线性dp,poj

题意：
有一个数组,每次可以把a[i]和a[i+1]合并起来,结果为a[i]-a[i+1],问你操作顺序,是最后一个数为他给定的那个数.

思路：
首先我们容易发现，这样n-1次操作下来，实质是对于n个数分配了+ -号，然后求和，当然第一个数肯定是+，第二个数和最后一个数肯定是负号
我们用dp[i][j]表示到第i个数时，总和是j的时候i的符号是什么，1/-1/0分别表示正 负和无法到达的状态

那么转移就显然了，对于一个存在的状态dp[i-1][j]，可以转移到dp[i][j+a[i]]=1和dp[i][j-a[i]]=-1

用ans[i]表示每个数的符号，最后倒序递推回去就可以，那么现在考虑怎么输出方案
我们发现，从左往右，我们先处理所有正号，每次都选择正号前面一个数，这样操作完后所有正号都会被翻转，负号同理
然后最后我们再一直选择第一个，就可以把之前翻转的符号返回到原来的为止了

因为有负数所以需要加回去

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;
const int maxn=110;
const int base=10005;
int dp[maxn][base<<1],ans[maxn],now,cnt,a[maxn];
int main()
{
   int n,t;
   scanf("%d%d",&n,&t);
   for(int i=1;i<=n;++i) 
       scanf("%d",&a[i]);
   dp[1][a[1]+base]=1;
   dp[2][a[1]-a[2]+base]=-1;
   for(int i=3;i<=n;++i)
       for(int j=-10000+base;j<=10000+base;++j){
           if(dp[i-1][j]!=0){ 
               dp[i][j+a[i]]=1;
               dp[i][j-a[i]]=-1; 
           } 
       } 
   now=t+base;
   for(int i=n;i>=2;--i){ 
       ans[i]=dp[i][now];
       if(ans[i]==1) 
           now-=a[i];
       else if(ans[i]==-1) 
           now+=a[i];
   } 
   int cnt=0;
   for(int i=2;i<=n;++i) 
       if(ans[i]==1){ 
          printf("%d\n",i-cnt-1);
          cnt++; 
       }
   for(int i=2;i<=n;++i) 
       if(ans[i]==-1)
          puts("1");
   return 0; 
}
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