大胆分析，勇敢地去把它抽象成模型
little_prince
2019-11-25 23:17:26
原题：POJ1722
acwing题面：《减操作》
**敢于向前闯才能创造奇迹！**
关于本题的做法因为有两篇题解，我自己就不再赘述，但是有很多的细节题解未能解释清楚，在这里作详细地补充。
先附上题解链接哈：
[题解1](https://www.acwing.com/solution/acwing/content/1670/)
[题解2（解释得稍微更清楚点，但是不如前者简单）](https://www.acwing.com/solution/acwing/content/2590/)
补充：
对于当前a[i]，如果最后的结果里前面是**负号**,那么应该在最后的**一直用第一个（即cut（1））的方法之前**未做任何处理；
如果最后的结果里a[i]前面是**正号**，**那么在之前作出的决策中，一定在i-1的位置cut过**，使得a[i]在当时阶段前面是负号，最后不断cut（1）时变成正号。
举个简单的例子：
a[1] a[2] a[3] a[4] a[5] a[6]
最后的结果如果a[4],a[6]前是正号（此处排开a[1],a[2]俩特例，题解中已讲到），即：
a[1]-a[2]-a[3]+a[4]-a[5]+a[6]
那么第一步，cut（3）和cut（5），变成
a[1] a[2] a[3]-a[4] a[5]-a[6]
发现妙处了吗？接下来一直cut（1）就能满足了哟！
那么关于输出“第一步”中cut的问题，
为什么是i-tot-1呢？
其实i-1就是刚刚我强调的东西啦。。（那么在之前作出的决策中，一定在i-1的位置cut过）
再减去一个tot是表示的剩下还有多少个数啦。。。
小结：
其实做这道题时没有怎么认真思考就去看了题解，至少以上这些经过我一段时间（尽管会很长）的认真思考还是可以想到的。说老实话，自己还是没有向前进的勇气。DP嘛，对自己好一点，能力尽管很差~~到现在还几乎没有自己独立写过一道DP~~，但来日方长，需要自己不懈地刷题，多思考。
最后附上自己的代码：
```
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int f=1,r=0;char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){r=r*10+c-'0';c=getchar();}
return f*r;
}
int cnt,n,sum,s,t,a[107],f[100007],flag;
int pd[100007];//1表示为负数， 0表示为正数
void dfs(int sum,int p){
if(flag) return;
if(sum == 0){
flag = 1;
return;
}
for(int i = p;i >= 3; i--)
{
if(flag) return;
if(sum - a[i] >= 0)
{
if(f[sum-a[i]])
{
pd[i] = 1;
dfs(sum - a[i],i-1);
if(flag) return;
pd[i] = 0;
}
}
}
}
int main(){
n=read();t=read();
for(int i = 1;i <= n; i++) a[i] = read(),sum += a[i];
s = ((sum - t) >> 1) - a[2];
f[0] = true;
pd[2] = 1;
for(int i = 3;i <= n; i++)
for(int j = s;j >= a[i]; j--)
f[j] |= f[j-a[i]];
dfs(s,n);
//for(int i = 1;i <= n; i++) printf("pd[%d] = %d\n",i,pd[i]);
for(int i = 2;i <= n; i++)
{
if(!pd[i])//正数
{
cout<<i - cnt - 1<<endl;
cnt++;
}
}
for(int i = 2;i <= n; i++)
if(pd[i]) cout<<1<<endl;
return 0;
}
```
_脚踏实地，方能仰望星空。_