题目链接:https://nanti.jisuanke.com/t/40854 题意:有n(n=1000)个纸牌,每个纸牌分为上下两格,且每格可有1-10个点,所有上格加起来的和为P1,所有下格加起来的和为P2,求想得到|P1-P2|的最小
题目链接:https://nanti.jisuanke.com/t/40854
题意:有n(n<=1000)个纸牌,每个纸牌分为上下两格,且每格可有1-10个点,所有上格加起来的和为P1,所有下格加起来的和为P2,求想得到|P1-P2|的最小值,需要翻转多少次
给出的题解是:
正常的做法是用 DP,可以用二维的 DP 数组,在这里用了一维数组进行 DP。 dp[i] 表示上下相差 时的最小操作次数。 因为是上下相差所以可能出现负数,将整个数组右移 位, 理论上是上下相差的最大值 在实际程序中 dp[i+N] 是上面 dp[i] 所表示的意义
每次翻转会使上下差值改变,这个改变值记录为 a[j],改变值应该是初始值的两倍。 状态转移方程就是 dp[i-a[j]]=min(dp[i-a[j]],dp[i]+1) 同时又考虑到差值有负数的情况,所以根据初始差值情况分类讨论一下,不同情况DP的方向 不同。
最后在 dp 数组中从 N 向两侧寻找能达到的最小值输出即可。
二维的代码也很好懂
#include<bits/stdc++.h> using namespace std; int dp[1005][20005]; int a[1005]; const static int INF=0x7fffff; int main() { int n; scanf("%d",&n); int tx=0,ty=0; for(int i=1;i<=n;i++) { register int x,y; scanf("%d %d",&x,&y); tx+=x; ty+=y; a[i]=(y-x)*2; } int t=tx-ty; int N=1000; for(int i=0;i<=1000;i++) for(int j=0;j<=20000;j++) dp[i][j]=INF; dp[0][t+N]=0; for(int i=1;i<=n;i++) { for(int j=0;j<=20000;j++) { if(j-a[i]>=0) { if(dp[i-1][j-a[i]]!=INF) dp[i][j]=min(dp[i-1][j],dp[i-1][j-a[i]]+1); else dp[i][j]=dp[i-1][j]; } } } int ans; for(int i=0;i<=1000;i++) { //cout<<dp[n][N-i]<<" "<<dp[n][N+i]<<" "; if(dp[n][N-i]!=INF||dp[n][N+i]!=INF) { ans=min(dp[n][N-i],dp[n][N+i]); break; } } cout<<ans; }
但在转换成一维的时候遇到不少问题,花了很多时间,第一个点在于一维的时候为了考虑a[i]的正负,还需要分情况讨论
第二个点在于分情况讨论后其状态转移方程还是得一致
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=1<<30; const int maxn=1e3+7; int a[maxn]; int dp[20010];//上下差为i(此时数组内数为10000+i)时的最小操作次数 int main(){ int n;scanf("%d",&n); int x,y,tx=0,ty=0; for(int i=1;i<=n;i++){ scanf("%d%d",&x,&y); tx+=x,ty+=y; a[i]=(y-x)*2;//每次翻牌,一增一减,故乘2 } int t=tx-ty; for(int i=0;i<=20000;i++)dp[i]=inf; dp[1000+t]=0;//初始状态 for(int i=1;i<=n;i++){ if(a[i]<=0){ for(int j=0;j<=20000+a[i];j++){ if(dp[j-a[i]]!=inf)dp[j]=min(dp[j],dp[j-a[i]]+1); } } else for(int j=20000;j>=a[i];j--){ if(dp[j-a[i]]!=inf)dp[j]=min(dp[j],dp[j-a[i]]+1); } } int ans; for(int i=0;i<=1000;i++){ //cout<<dp[10000+i]<<" "<<dp[10000-i]<<endl; if(dp[1000+i]!=inf||dp[1000-i]!=inf){ ans=min(dp[1000+i],dp[1000-i]); break; } } cout<<ans<<endl; return 0; }