POJ 1722 SUBTRACT

给定一个数组a[1,2,..,n] 。定义数组第i位上的减操作：把ai和ai+1换成ai - ai+1。输入一个n位数组以及目标整数t，求一个n-1次操作序列，使得最后剩下的数等于t
最后输出依此操作的i

输入：第一行一个N，一个T,接下来N行，每行一个正整数ai
输出：依次输出被操作的位置i

首先对题目进行分析后，似乎没有什么好的思路。
从结果入手。
对于最后的得到的整数，肯定是将原数列中一些数前加上了符号，然后将数列加在一起的操作。
这样我们就避免了麻烦的数组操作。‘

这样我们将题目转换成了：
一个数列[a1, a2, ....aN]，对于数组中的数，将部分正整数变为负数，使整个数组的和为t，最后输出将哪些数变为负数
其中，从原题中我们可以知道:由于第1个数前没有数，所以第1个数不可能加负数，这样我们想，假设最后剩下两个数a1, a2,由原题目我们知道，要想把这两个数化为一个整数，第二个数必须为负数。
因此，在最初，第一个数必须为正，第二个数必须为负数。

然后整理能够描述状态空间的信息：
1.一个正整数i,表示进行到了第i个数
2.标记-1或1，表示第i个数取负还是取正
3.一个整数，表示进行到第i个数时，前i个数的和

接着我们要确定的是第i个数取正还是取负，然后我们还需要前i-1个数的和，但是我们能够注意到的是，前i-1个数的和是不确定的，对于i前的除了1，2位置的数，每一个数都有取正和取负两个操作，由于i可能很大
因此前i-1个数的和的结果也很多，所以对于i-1个数的和是不确定的，而对于第i个数取正还是取负，一共只有两个情况。
这样我们只能将前i-1个数的和作为变量，加一个维度，用来描述状态空间。
设f[i, j] = k表示到第i个数，前i个数的和为j时，第i个数的标记为k
这样问题的重点就在于如何记录路径了
对于我们的思路肯定是倒推回去
我们试着从f[][t]推回去
但是对于第一维，我们是并不确定的，
我们只能试着将i从2到n一个一个搜，但是注意的是i不能从1开始，最后我们处理1时再说原因
我们从我们的策略分析:我们可以发现，我们首先需要输出的显然是一路倒推后标记为1的i值，但是我们有一点就是我们每操作一个i，i之后的数的下标会全部减1。
因此首先我们首先要从答案一路逆推回去，同时开一个新数组，在第i个位置标记这个数是取正还是取负。
然后首先输出所有标记取正的下标，但是我们知道一个操作结束后后面的下标会变，所以我们设一个新的变量记录在某个位置之前操作了多少次，例如：我们设我们现在第i个位置，前面操作了cnt次，这样i的下标就应该因为操作而被迫变更了cnt次，但是观察样例的推断我们可以发现，在样例中，原本i = 2时，i = 2理当是正的，但是在最初我们全部将i = 2的情况标记为负了，所以这就是说，类推到所有情况，所有取正的下标，在原题i和i+1的
情况中，实际上取正的是i+1，所以对于取正的位置的下标，除了要减去cnt外，还要再减去1
最后我们讨论输出1的情况，我们相当我们吧所有取正的情况输出后，操作次数cnt,很可能（很大可能）并不到n-1，一方面是因为刚才我们没有输出1，但另一方面，存在cnt与n-1的差距不止1，这种情况说明在最后，在进行了全部的操作后，最后所有剩下的数不再进行取正操作，也就是说除了1之外全部取为了负数，例如： 1 2 3 4 5 6 ，除了1之外，2,3,4,5,6全部标成取负号，这意味着在这些操作中，所有的i全部取为1，所以我们就要输出
n-1-cnt个1，当然也可以是在所有在标记为取负的位置输出'1'，但是我们上面说了因为2的符号强制取负的关系，下标除了减去cnt还要再减去1，但是1是不受影响的，原因非常简单:下标1在下标2之前，所以下标1不受下标2的影响

最后顺便批判一番！AC程序过不了样例系列！！！！！！

 #include<iostream>

 #include<iomanip>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<ctime>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 const int maxn = ;

 const int maxt = ;

 const int quz = ;

 int n, t;

 int f[maxn][maxt];

 int a[maxn];

 int ans[maxn];

 inline int read() {

     int x = , y = ;

     char ch = getchar();

     while(!isdigit(ch)) {

         if(ch == '-') y = -;

         ch = getchar();

     }

     while(isdigit(ch)) {

         x = (x << ) + (x << ) + ch - '';

         ch = getchar();

     }

     return x * y;

 }

 int main() {

     memset(f, , sizeof(f));

     n = read(), t = read();

     for(int i = ; i <= n; ++i)

         a[i] = read();

      f[][a[] + quz] = ;

      f[][a[] - a[] + quz] = -;

      for(int i = ; i <= n; ++i)

          for(int j = - + quz; j <=  + quz; ++j) {

              if(f[i - ][j] != ) {

                  f[i][a[i] + j] = ;

                  f[i][j - a[i]] = -;

              }

          }

     int s = quz + t;

     for(int i = n; i >= ; --i) {

         ans[i] = f[i][s];

         if(ans[i] == )

             s -= a[i];

         else if(ans[i] == -)

             s += a[i];

     }

     int cnt = ;

     for(int i = ; i <= n; ++i)

         if(ans[i] == ) {

             cout << i - cnt -  << '\n';

             cnt++;

         }

     for(int i = ; i <= n; ++i)

         if(ans[i] == -)

             cout <<  << '\n';

 /*    for(; cnt + 1 <= n - 1; cnt++)

         cout << 1 << '\n';*/

     return ;

 }

巴特西

POJ 1722 SUBTRACT

最新文章

热门文章