244 条题解
-
28PowderHan LV 10 @ 2017-05-07 13:04:04
/* 好题~一个很经典的dp 状态和状态转移都很巧妙~ 首先我们定义f[i][j]表示 到第i块水晶堆成高度差为j的双塔时,较矮塔的高度最大值 这样我们成功地将问题转换为了最优性问题 这样就可以尝试用DP来解决了~ 既然想到了这样的状态表示必然是不难想到决策的 考虑到每个状态都可以由四个决策而来~ (这个时候最好自己拿起笔来画图手算模拟) 对于第i块水晶 1.不选取这块水晶 f[i-1][j] 2.将这块水晶放在高塔上 f[i-1][j-h[i]] j-h[i]>=0 3.将这块水晶放在低塔上并且不改变高低塔关系 f[i-1][j+h[i]]+h[i] j+h[i]<=s[i-1] 4.将这块水晶放在低塔上且改变了高低塔关系 f[i-1][h[i]-j]+h[i]-j h[i]-j>=0 这样我们就可以直接开始转移了~ 这里需要好好手算理解一下 同时注意到如果一个f[i][j]是还未到到达的状态~ 那么必然是不可行的 如果f[][]初始化为0那么可能某个f[i][j]是由一个本来无法到达的转移而来~ 那么必然是不合法的 就像0/1背包中的要求装满的情况一样 我们应该将f[][]初始化为-INF 同时初值f[0][0]=1 同时注意几个限制条件 最终答案是 如果f[n][0]为0说明是不可行的输出无解 (注意因为不是-INF因为一直不选木块也可以成功转移到f[n][0]只是值为0) 不然最终答案就是f[n][0] */ #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXN=105; const int MAXH=2005; int f[MAXN][MAXH]; int h[MAXN]; int s[MAXN]; int n; void init() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&h[i]); s[i]=s[i-1]+h[i];//维护前缀和 } } inline void update(int& i,int& j) { f[i][j]=f[i-1][j];//不放 int h1=j-h[i];//放在高塔 if(h1>=0)//限制条件 f[i][j]=max(f[i][j],f[i-1][h1]); int h2=j+h[i];//放在低塔未改变高矮关系 if(h2<=s[i-1])//必须h2要小于s[]限制条件 f[i][j]=max(f[i][j],f[i-1][h2]+h[i]); int h3=h[i]-j;//放在低塔改变了高矮关系 if(h3>=0)//限制条件 f[i][j]=max(f[i][j],f[i-1][h3]+h3); } void DP() { memset(f,-0x3f,sizeof(f)); f[0][0]=0; for(int i=1;i<=n;i++)//由初始推向末尾 for(int j=0;j<=s[i];j++)//j从0到s[i]才可行 update(i,j); if(!f[n][0])//判断是否有解 printf("Impossible\n"); else printf("%d\n",f[n][0]); } int main() { init(); DP(); } /* 最朴素最简单做法~ 数据弱是可以过的而且也不卡时间 但是如果数据加强估计就不行了~~ 预期得分65~70但是却无压力AC... #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXN=105; const int MAXV=2005; int f[MAXV][MAXV]; int h[MAXN]; int sum; int n; void init() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&h[i]); sum+=h[i]; } } void DP() { f[0][0]=1; for(int k=1;k<=n;k++) for(int i=sum;i>=0;i--) for(int j=sum;j>=0;j--) if(f[i][j]) { f[i+h[k]][j]=1; f[i][j+h[k]]=1; } for(int i=sum;i>=1;i--) if(f[i][i]) { printf("%d\n",i); return; } printf("Impossible\n"); } int main() { init(); DP(); }*/ /* 同时看到某神犇给出了上面思想代码的bitset优化~ 这里就直接贴出来了 速度还是蛮快的 #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<bitset> using namespace std; int w[105],n,h[105],sum=0; int main() { scanf("%d",&n); for (int i=1;i<=n;i++)scanf("%d",&w[i]),sum+=w[i]; bitset<3000> f[3000]; for (int i=0;i<=sum;i++) f[i].reset(); f[0].set(1); for (int i=1;i<=n;i++) { for (int j=sum;j>=0;j--) if (f[j].any()) { f[j+w[i]]=f[j]|f[j+w[i]];//位运算的精髓 f[j]=f[j]|(f[j]<<w[i]);//精髓! } } int ans; for (ans=sum;ans>0;ans--) if (f[ans].test(ans+1)) break; if (ans) printf("%d",ans);else printf("Impossible"); return 0; } */
-
102018-08-12 14:36:32@
上面大佬太强了
我因为非常弱只好写了个暴力的DP#include<iostream> using namespace std; int dp[5010][5010],h[110]; int main() { int n,i,j,k,sum=0; cin>>n; for(i=1;i<=n;i++) cin>>h[i]; dp[0][0]=1; for(i=1;i<=n;i++) { for(j=sum;j>=0;j--) for(k=sum;k>=0;k--) { if(dp[j][k]) { dp[j+h[i]][k]=1; dp[j][k+h[i]]=1; } } sum+=h[i]; } for(i=sum;i>0;i--) if(dp[i][i]) { cout<<i; return 0; } cout<<"Impossible"; return 0; }
-
42017-11-06 23:57:49@
2000的数据,想都没想直接暴力dp,其实可能说是递推更恰当点……
翻开题解发现更好的做法……#include <iostream> #include <cstring> using namespace std; bool d[2001][2001];//d[i][j]=d[i-h[k]][j]||d[i][j-h[k]]||d[i][j] long h[201]; int main() { long n,i,j,k; cin>>n; for (i=1;i<=n;i++) cin>>h[i]; memset(d,false,sizeof(d)); d[0][0]=true; for (k=1;k<=n;k++) for (i=2000;i>=0;i--) for (j=2000;j>=0;j--){ if (i>=h[k]) d[i][j]=d[i][j] || d[i-h[k]][j]; if (j>=h[k]) d[i][j]=d[i][j] || d[i][j-h[k]]; } for (i=2000;i>=1;i--) if (d[i][i]) {cout<<i; return 0;} cout<<"Impossible\n"; return 0; }
-
32019-03-09 15:44:15@
按照PowderHan大牛的思路写了一下。
#include<bits/stdc++.h> using namespace std; int N,h[105]; int dp[105][2005]; const int inf = 0x3f3f3f; int main(){ memset(dp,-inf,sizeof(dp)); scanf("%d",&N); for(int i=1;i<=N;i++){ scanf("%d",h+i); } dp[0][0] = 0; for(int i=1;i<=N;i++){ for(int j=0;j<=sum[i];j++){ int dif = j-h[i],add = j+h[i]; if(dif>=0) dp[i][j] = max(dp[i-1][j],dp[i-1][j-h[i]]); //加到高处 else dp[i][j] = max(dp[i-1][j],dp[i-1][-dif]-dif); //加到矮处且改变了相对关系 dp[i][j] = max(dp[i][j],dp[i-1][add]+h[i]); //加到矮处且不改变相对关系 } } if(dp[N][0]) printf("%d",dp[N][0]); else printf("Impossible"); return 0; }
-
32017-10-29 09:29:02@
//这大概是最快的了qwq
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,sum,h[105],f[2005][2],s;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d",&h[i]);
s+=h[i];
}
memset(f,-1,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;++i)
{
sum=min(sum+h[i],s/2);
for(int j=0;j<=sum;++j)
f[j][i&1]=-1;
for(int j=0;j<=sum;++j)
if(f[j][1^(i&1)]>=0)
{
f[j][i&1]=max(f[j][i&1],f[j][1^(i&1)]);
if(j>h[i])
f[j-h[i]][i&1]=max(f[j-h[i]][i&1],f[j][1^(i&1)]+h[i]);
else
f[h[i]-j][i&1]=max(f[h[i]-j][i&1],f[j][1^(i&1)]+j);
f[j+h[i]][i&1]=max(f[j+h[i]][i&1],f[j][1^(i&1)]);
}
}
if(!f[0][n&1])
{
puts("Impossible");
return 0;
}
printf("%d",f[0][n&1]);
return 0;
} -
22020-01-12 13:35:52@
来波dp
#include<iostream> using namespace std; int n, a[105]; bool dp[105][105]; int main() { cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; dp[0][0] = true; for(int i = 1; i <= n; i++) for(int j = 1000; j >= 0; j--) for(int k = 1000; k >= 0; k--) { if(j >= a[i]) dp[j][k] |= dp[j - a[i]][k]; if(k >= a[i]) dp[j][k] |= dp[j][k - a[i]]; } for(int i = 1000; i >= 1; i--) if(dp[i][i] == true) { cout << i << endl; return 0; } cout << "Impossible" << endl; return 0; }
二维dp,有待降维
-
22017-09-13 12:16:08@
-
12020-06-26 20:11:08@
dp
f[i][j]表示使用前j个方块搭出高度差为i的双塔时较矮塔的最大高度#include<iostream> using namespace std; int f[4010][110]; int h[110]; int main() { int INF = 2000000000; int n; cin >> n; for (int i = 0; i < n; i++) cin>>h[i]; for (int i = 1; i <= 4000; i++) f[i][0] = -INF; f[0][0] = 0; for (int j = 1; j <= n; j++) for (int i = 0; i <= 2000; i++) { // j - 1? f[i][j] = max(f[i][j-1], f[i+h[j-1]][j-1]+h[j-1]); if (h[j-1] <= i) f[i][j] = max(f[i-h[j-1]][j-1], f[i][j]); else f[i][j] = max(f[h[j-1]-i][j-1]+h[j-1]-i, f[i][j]); } if (f[0][n]<=0) cout<<"Impossible"; else cout<<f[0][n]; return 0; }
-
02020-02-11 14:03:45@
C++
3种情况讨论:
cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int mx(int a,int b){return a>b?a:b;}
int n,h[105],s[105],f[105][2005];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i]);
s[i]=s[i-1]+h[i];
}
memset(f,-0x7f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=s[i];j++)
{
f[i][j]=f[i-1][j];
int h1=j-h[i];
if(h1>=0)
f[i][j]=mx(f[i][j],f[i-1][h1]);
int h2=j+h[i];
if(h2<=s[i-1])
f[i][j]=mx(f[i][j],f[i-1][h2]+h[i]);
int h3=h[i]-j;
if(h3>=0)
f[i][j]=mx(f[i][j],f[i-1][h3]+h3);
}
}
if(!f[n][0])
printf("Impossible\n");
else
printf("%d\n",f[n][0]);
return 0;
}
-
02019-02-10 10:32:07@
记录所有可以到达的高度的次数,可以构建双塔的高度(high)到达次数>=2,同时满足2*high的高度到达次数>=1。
program vijos1037(Freewing);
uses math;
var f:array [0..10000] of longint;
i,j,n,h,sum,ans:longint;begin
readln(n);
fillchar(f,sizeof(f),0);
f[0]:=1;
sum:=0;
for i:=1 to n do begin
read(h);
inc(sum,h);
for j:=2000 downto h do
if f[j-h]>=1 then inc(f[j]);
end;
sum:=sum>>1;
for i:=sum downto 0 do
if (f[i]>=2) and (f[i<<1]>=1) then begin
ans:=i;
break;
end;
if ans>0 then write(ans) else write('Impossible');
end. -
02018-11-04 13:53:50@
c++代码
#include<bits/stdc++.h>
using namespace std;
int n,sum,ans,a[101];
bool f[101][1001][1001];//f[k][i][j]表示用前i块水晶能否搭建高度分别为i,j的双塔
//一定要用bool,不然会爆内存
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
f[0][0][0]=1;
for(int k=1;k<=n;k++)
for(int i=0;i<=sum/2;i++)
for(int j=0;j<=sum/2;j++){
f[k][i][j]=f[k-1][i][j];
if(i>=a[k]) f[k][i][j]|=f[k-1][i-a[k]][j];
if(j>=a[k]) f[k][i][j]|=f[k-1][i][j-a[k]];
}
for(int i=sum/2;i>=1;i--)
if(f[n][i][i]){
ans=i;
break;
}
if(ans) printf("%d",ans);
else printf("Impossible");
return 0;
} -
02018-05-07 14:56:09@
水,就是递推,刷表格
#include<bits/stdc++.h>
using namespace std;
int n,H[250],d[2001][2001],i,j,k;
int main(){
cin>>n;
d[0][0]=1;
for(i=1;i<=n;i++){
cin>>H[i];
for (j=2000;j>=0;j--)
for (k=2000;k>=0;k--){
if (j>=H[i]) d[j][k]=max(d[j][k],d[j-H[i]][k]);
if (k>=H[i]) d[j][k]=max(d[j][k],d[j][k-H[i]]);
}
}
for (i=2000;i>=1;i--)
if(d[i][i]){cout<<i;return 0;}
puts("Impossible");
return 0;
} -
02017-07-20 14:35:54@
#include <stdio.h> #include <math.h> #include <stdlib.h> #include <string.h> #include <string> #include <algorithm> #include <iostream> #include <ctype.h> #include <set> #include <map> #include <vector> #include <stack> #include <queue> #define left (now<<1) #define right ((now<<1)+1) #define mid ((l+r)>>1) #define fst first #define snd second using namespace std; typedef long long lint; int dp[110][1010],n; int main(){ scanf("%d",&n); memset(dp,-1,sizeof(dp)); for(int i = 0; i <= n; ++i){ dp[i][0] = 0; } for(int i = 1; i <= n; ++i){ int num; scanf("%d",&num); for(int j = 0; j <= 1000; ++j){ if(j + num <= 1000 && dp[i-1][j+num] != -1){ dp[i][j] = max(dp[i][j],dp[i-1][j+num] + num); } if(j - num >= 0 && dp[i-1][j-num] != -1){ dp[i][j] = max(dp[i][j],dp[i-1][j-num]); } if(num - j >= 0 && dp[i-1][num-j] != -1){ dp[i][j] = max(dp[i][j],dp[i-1][num-j] + (num - j)); } dp[i][j] = max(dp[i][j],dp[i-1][j]); } } dp[n][0]==0?printf("Impossible\n"):printf("%d\n",dp[n][0]); return 0; }
-
02016-12-23 20:01:17@
过五十纪念!!!!!!!!!!
状态转移好像很难写,所以我这几天都在想这道题。首先可以分析出主要要考察他们之间的高度差,因为有答案的话最终高度差为0, 无答案的话就可以令他为一个小于0的数。就是f[i][j]表示前i个水晶放完之后塔高度差为j的较矮的塔的高度(之前我写的是j为较矮的塔,f表示高度差,但写起来非常冗长,看了题解把改了就十分好写了),然后很容易想到他的状态和i-1的状态有关,有两个子状态:放或不放,其中放又有两个个子状态:放高塔,放矮塔,其中放矮塔还有两个子状态:放矮塔后矮塔还是矮塔,放矮塔后原来的高塔变成矮塔,这样状态就考虑完全了,只需用前一个状态的j即可。但是前一个j是有范围的,它必须大于0小于sum[i-1](部分和),这是显然的否则不合理。然后初始化有个地方一开始没看出来就是f[1][a[1]]=0因为i直接从2开始那么一的所有所有情况都必须已经有答案。最后有个非常恶心的地方,能过样例但是总是WA就是f数组初始化必须全部搞成负无穷而不是-1(我一开始闭着眼睛写-1最后怎么也没想到初始化错了)因为负是一种状态,而如果是-1
的话他可以通过前一种-1的情况加一些东西就变成正的了,这是不可能的应为如果母状态是负的话(即无答案)子状态就不可能出答案也就不可能是正的,所以这个地方非常恶心,看题解才解决。参考代码:(已AC)
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;int f[205][2005], sum[205], a[205];
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;for (int i=1;i <= n;i++) {
cin >> a[i];
}
sort(a+1, a+n+1);
sum[0]=0;
for (int i=1;i <= n;i++) {
sum[i]=sum[i-1]+a[i];
}memset(f, -0x7f, sizeof(f));
f[1][0]=0;
f[1][a[1]]=0;for (int i=2;i <= n;i++) {
for (int j=0;j <= sum[i];j++) {
int h1=j-a[i];
if (h1 >= 0 && h1 <= sum[i-1]) {
f[i][j]=max(f[i-1][h1], f[i][j]);
}int h2=j+a[i];
if (h2 <= sum[i-1]) {
f[i][j]=max(f[i-1][h2]+a[i], f[i][j]);
}int h3=a[i]-j;
if (h3 >= 0 && h3 <= sum[i-1]) {
f[i][j]=max(f[i-1][h3]+h3, f[i][j]);
}int h4=j;
if (h4 <= sum[i-1])
f[i][j]=max(f[i-1][h4], f[i][j]);
}
}if (f[n][0] <= 0) {
cout << "Impossible";
} else cout << f[n][0];return 0;
} -
02014-08-21 16:57:13@
include <iostream>
include <cstdio>
include <cstring>
using namespace std;
int n, sum = 0;
int f[101][2001], c[101];
int main()
{
scanf("%d", &n);for(int i = 1; i <= n; i++)
{
scanf("%d", &c[i]);
sum = sum + c[i];
}memset(f, -1, sizeof(f));
f[0][0] = 0;for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= sum; j++)
{
if(f[i - 1][j] != -1) f[i][j] = f[i - 1][j];if(j + c[i] <= sum && f[i - 1][j + c[i]] != -1) f[i][j] = max(f[i][j], f[i - 1][j + c[i]] + c[i]);
if(j >= c[i] && f[i - 1][j - c[i]] != -1) f[i][j] = max(f[i][j], f[i - 1][j - c[i]]);
if(c[i] > j && f[i - 1][c[i] - j] != -1) f[i][j] = max(f[i][j], f[i - 1][c[i] - j] + c[i] - j);
}
}if(f[n][0] > 0) printf("%d", f[n][0]);
else printf("Impossible\n");return 0;
} -
02014-02-11 20:48:51@
此题还行,我一开始用的普通的背包写法,看了别人的题解后很受启发
于是又写了一个AC程序。思路下面的链接里有 -
02014-01-01 11:58:54@
Vijos 题解:http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步 -
02014-01-01 11:57:36@
Vijos 题解:http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步 -
02013-11-29 13:47:34@
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int f[111][2222], c[111];
int main()
{
scanf("%d", &n);
int sum = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d", &c[i]);
sum += c[i];
}
memset(f, -1, sizeof(f));
f[0][0] = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 0; j <= sum; j++)
{
if(f[i - 1][j] != -1) f[i][j] = f[i - 1][j];
if(j + c[i] <= sum && f[i - 1][j + c[i]] != -1)
f[i][j] = max(f[i][j], f[i - 1][j + c[i]] + c[i]);
if(j >= c[i] && f[i - 1][j - c[i]] != -1)
f[i][j] = max(f[i][j], f[i - 1][j - c[i]]);
if(c[i] > j && f[i - 1][c[i] - j] != -1)
f[i][j] = max(f[i][j], f[i - 1][c[i] - j] + c[i] - j);
}
}
if(f[n][0] > 0) printf("%d\n", f[n][0]);
else printf("Impossible\n");
return 0;
} -
02013-08-09 22:00:43@
var
n,s,w,j,k,p,q,i:longint;
f:array[0..2001,0..2001] of boolean;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;function min(a,b:longint):longint;
begin
if a>b then exit(b)
else exit(a);
end;
begin
readln(n);
f[0,0]:=true;
for i:=1 to n do
begin
read(w);
s:=s+w;
for j:=s downto 0 do
for k:=j downto 0 do
if f[j,k] then
begin
p:=j+w; q:=k+w;
if p<=s then f[p,k]:=true;
if q<=s then f[max(q,j),min(q,j)]:=true;
end;
end;
for i:=s downto 0 do
if f[i,i] then break;
if i=0 then writeln('Impossible')
else writeln(i);
end.