题解

241 条题解

  • 20
    @ 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;  
    }  
    */
    
    • @ 2017-11-10 07:42:58

      放在高塔上为什么是减,放在底塔上为什么是加,不应该反过来吗

    • @ 2018-02-19 14:10:37

      @yyyz108: 是回归上一个状态的,的确有点难想,但是还是自己多理解几遍好~

    • @ 2019-02-12 07:49:58
      /*
      同时初值f[0][0]=1
      */
      

      应该是

      /*
      同时初值f[0][0]=0
      */
      
  • 5
    @ 2018-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;
    }
    
  • 3
    @ 2017-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;
    }
    
  • 2
    @ 2017-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;
    }

  • 1
    @ 2019-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;
    }
    
  • 0
    @ 2019-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.

  • 0
    @ 2019-01-09 11:51:49
    import java.lang.Math.*;
    import java.util.*;
    import java.io.*;
    
    public class Main {
        public static void main(String[] args) throws IOException {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] height = new int[n + 1];
            int i;
            for (i = 1; i <= n; i++) height[i] = sc.nextInt();
            int ans = maxDoubleTower(height, n);
            if (ans == -1) {
                System.out.println("Impossible"); 
                return;
            }
            System.out.println(ans);
        }
        
        public static int maxDoubleTower(int[] height, int n) {
            int[][] dp = new int[n + 1][2048];
            int[] s = new int[n + 1];
            int i, j;
            for (i = 1; i <= n; i++) {
                s[i] = s[i-1] + height[i];
            }
            
            for (i = 0; i <= n; i++) {
                for (j = 0; j <= 2047; j++) dp[i][j] = -2048;
            }
            dp[0][0] = 0;
            for (i = 1; i <= n; i++) {
                for (j = 0; j <= s[i]; j++) {
                    dp[i][j] = dp[i-1][j];
                    if (j >= height[i]) {
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j-height[i]]);
                    }
                    
                    if (j <= height[i]) {
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][height[i]-j] + height[i] - j);
                    }
                    
                    if (j + height[i] <= s[i-1]) {
                        dp[i][j] = Math.max(dp[i][j], dp[i-1][j + height[i]] + height[i]);
                    }
                }
            }
            
            return (dp[n][0] > 0 ? dp[n][0] : -1);
        }
    }
    /*
    s[i] refers to the sum of crystal from 1 to i
    dp[i][j] refers to the maximum height of the lower tower when using the first
    i pieces of crystal and with a height difference of j
    case 1: ignore piece i dp[i][j] = dp[i-1][j]
    case 2: put on the higher tower dp[i][j] = dp[i-1][j-height[i]]  condition j >= height[i]
    case 3: put on the lower tower without changing the height order
        dp[i][j] = dp[i-1][j+height[i]] + height[i] condition j+height[i] <= s[i]
    case 4: put on the lower tower but the lower tower becomes the taller one
        dp[i][j] = dp[i-1][height[i] - j] + height[i] - j condition height[i] >= j
    */
    
    
    
  • 0
    @ 2018-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;
    }

  • 0
    @ 2018-06-03 20:45:09

    分析后这道题其实很简单
    其实我的程序有点**暴力枚举**的思想(受到了机房某大佬启发)
    var n,i,j,k,m,v:longint;
    a:array[0..10000] of longint;
    f:array[0..2000,0..2000] of boolean;
    begin
    readln(n);
    for i:=1 to n do
    read(a[i]);
    f[0,0]:=true;
    for i:=1 to n do
    begin
    m:=m+a[i];
    for j:=m downto 0 do
    for k:=m downto 0 do
    if f[j,k]=true then
    begin
    f[j+a[i],k]:=true;
    f[j,k+a[i]]:=true;
    end;
    end;
    for i:=m downto 1 do
    if f[i,i] then
    begin
    writeln(i);
    halt;
    end;
    writeln('Impossible');
    end.

  • 0
    @ 2018-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;
    }

  • 0
    @ 2017-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;
    }
    
    • @ 2018-08-10 10:22:33

      这头文件是万能的吧!

  • 0
    @ 2016-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;
    }

  • 0
    @ 2015-10-08 20:18:59

    program vijos1037;
    var
    f:array[0..100,0..2000] of longint;
    ans,n,m,i,j,k,hh:longint;
    h:array[0..100] of longint;
    procedure init;
    begin
    readln(n);
    for i:=1 to n do
    begin
    read(h[i]);
    hh:=h[i]+hh;
    end;
    end;
    function max(a,b:longint):longint;
    begin
    if a>b then exit(a) else exit(b);
    end;
    procedure work;
    begin
    for i:=0 to n do
    for j:=0 to hh do
    f[i,j]:=-maxlongint;
    f[0,0]:=0;
    for i:=1 to n do
    for j:=hh downto 0 do
    begin
    if j>h[i] then
    f[i,j]:=max(f[i-1,j],max(f[i-1,j-h[i]]+h[i],f[i-1,j+h[i]]));
    if j<=h[i] then
    f[i,j]:=max(f[i-1,j],max(f[i-1,h[i]-j]+j,f[i-1,h[i]+j]));
    end;
    ans:=f[n,0];
    if f[n,0]<=0 then writeln('Impossible') else write(ans);
    end;
    begin
    init;
    work;
    end.

  • 0
    @ 2014-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;
    }

  • 0
    @ 2014-02-11 20:48:51

    此题还行,我一开始用的普通的背包写法,看了别人的题解后很受启发
    于是又写了一个AC程序。思路下面的链接里有

    两种方法思路介绍+AC代码

  • 0
    @ 2014-01-01 11:58:54

    Vijos 题解:http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
    有疑问请留言 共同进步

  • 0
    @ 2014-01-01 11:57:36

    Vijos 题解:http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
    有疑问请留言 共同进步

    • @ 2016-04-04 13:02:01

      题解页面不存在啊!!!!

  • 0
    @ 2013-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;
    }

  • 0
    @ 2013-09-18 15:17:44

    var
    a:array[0..100] of longint;
    f:array[0..2000,0..2000] of boolean;
    i,j,k,sum,n:longint;
    begin
    readln(n);
    for i:=1 to n do
    read(a[i]);
    f[0,0]:=true;
    for i:=1 to n do
    begin
    for j:=sum downto 0 do
    for k:=sum downto 0 do
    if f[j,k] then
    begin
    f[j,k+a[i]]:=true;
    f[j+a[i],k]:=true;
    end;
    sum:=sum+a[i];
    end;
    for i:=sum downto 1 do
    if f[i,i] then
    begin
    writeln(i);
    halt;
    end;
    writeln('Impossible');
    end.

信息

ID
1037
难度
6
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
9715
已通过
2551
通过率
26%
被复制
1
上传者