解题思路:
原博客地址在此!
参考代码:
#include <bits/stdc++.h> using namespace std; const int maxn = 1000 + 10; const int INF = 0x3f3f3f3f; int n,s = 0; int a[maxn],b[maxn],dp[maxn][maxn*6+10]; int main(){ scanf("%d",&n); for(int i = 1; i <= n; i++) { scanf("%d%d",&a[i],&b[i]); s += a[i] + b[i]; } memset(dp,INF,sizeof(dp)); dp[1][a[1]] = 0; dp[1][b[1]] = 1; for(int i = 2; i <= n; i++) for(int j = 0; j <= 6*n; j++) { if(j >= a[i]) dp[i][j] = min(dp[i][j],dp[i-1][j-a[i]]); if(j >= b[i]) dp[i][j] = min(dp[i][j],dp[i-1][j-b[i]] + 1); } int ans = INF,anst = INF; for(int j = 0; j <= s; j++) if(dp[n][j] < INF) if(anst > abs(s-j-j)) anst = abs(s-j-j), ans = dp[n][j]; else if(anst == abs(s-j-j)) ans = min(ans,dp[n][j]); printf("%d\n",ans); return 0; }
0.0分
7 人评分
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:575 |
C语言训练-角谷猜想 (C++代码)(3N+1问题)浏览:1750 |
C语言程序设计教程(第三版)课后习题8.4 (Java代码)浏览:730 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:521 |
C语言程序设计教程(第三版)课后习题11.1 (C语言代码)浏览:792 |
奖学金 (C++代码)浏览:2005 |
【计算两点间的距离】 (C语言代码)浏览:883 |
WU-图形输出 (C++代码)浏览:802 |
WU-陶陶摘苹果2 (C++代码)浏览:973 |
2004年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:503 |