花了好长时间终于写出了这道题, 主要是状态转移方程比较奇葩, 类似于背包问题, 难以想到.
呃呃, 写得 DP 不多, 对于如何想出状态转移方程还没什么心得, 主要是往之前见过的模型上靠. 这道题的话, 其实可以稍微转化一下设问, 变成有 n 个数, 每次操作可以将其变为相反数, 问最少操作几次可以使总和的绝对值最小. 设 dp[i][j] 为考虑到第 i 个数, 总和为 j 时最少的操作次数. 状态转移方程为 dp[i][j]=min(dp[i-1][j-num[i]],dp[i-1][j+num[i]]+1). 因为是取最小值, 一开始要把 dp 数组初始化成 inf, 还要将 dp[0][0] 初始化成 0. 反正代码细节也还是有的.
- #include<cstdio>
- #include<cstring>
- const int maxn=1e3+5,maxm=1e4+5,inf=0x3f3f3f3f;
- int n,num[maxn],dp[maxn][maxm],mm[maxn],ans;
- inline int abs(int x) {return x>0?x:-x;}
- inline int map(int x) {return x+5e3+1;}
- inline int min(int a,int b) {return a<b?a:b;}
- int main() {
- scanf("%d",&n);
- int a,b,sum=0;
- for(int i=1;i<=n;++i) {scanf("%d%d",&a,&b);num[i]=a-b;}
- memset(dp,inf,sizeof(dp));
- for(int i=0;i<=n;++i) {dp[i][map(sum)]=0;sum+=num[i];mm[i]=mm[i-1]+abs(num[i]);}
- for(int i=1;i<=n;++i)
- for(int j=-mm[i];j<=mm[i];++j)
- dp[i][map(j)]=min(dp[i-1][map(j-num[i])],dp[i-1][map(j+num[i])]+1);
- for(int i=0;i<=mm[n];++i)
- if(dp[n][map(i)]!=inf||dp[n][map(-i)]!=inf) {
- ans=min(dp[n][map(i)],dp[n][map(-i)]);
- break;
- }
- printf("%d",ans);
- return 0;
- }
AC 代码
来源: http://www.bubuko.com/infodetail-2760061.html