acdream 1429 Rectangular Polygon【dp】

男娘i 2022-08-14 04:46 150阅读 0赞

题目：[acdream 1429 Rectangular Polygon][]

题意：给出n个数，是边长，然后问你能不能组成多边形，其边必须是平行于x轴或者平行于y轴的。如果可以的话输出任意一种方案。

分析：分析发现，就是给你一堆数，然后让你尽可能挑出多的数，分成两部分的和相等，我们可以用dp来解决这个问题。

定义dp【i】【j】 前 i 个数中挑出一些书其两部分的差值是 j 的最大个数。

转移方程：

dp[i][j] = max(dp[i][j],dp[i-1][j]);  //不放
                      dp[i][j-a[i]] = max(dp[i][j-a[i]],dp[i-1][j]+1); //放入第二堆
                      dp[i][j+a[i]] = max(dp[i][j+a[i]],dp[i-1][j]+1);  //放入第一堆

然后记录路径，输出来就可以了。

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    using namespace std;
    typedef long long ll;
    const int N = 55000;
    const int M = 125;
    int num[M];
    bool ok[N];
    int dp[M][N];
    int fa[M][N];
    
    vector<int> one,two;
    int main()
    {
        //freopen("Input.txt","r",stdin);
        int n;
        while(~scanf("%d",&n))
        {
            int sum = 0;
            for(int i = 1; i <= n; i++)
            {
                scanf("%d", &num[i]);
                sum += num[i];
            }
            int l = 30000 , r = 30000 ;
            memset(dp, -1, sizeof(dp));
            dp[0][30000] = 0;
            for(int i = 1; i <= n; i++)
            {
                for(int j = l; j <= r; j++)
                {
                    if(dp[i-1][j] <= -1) 
                        continue;
                    if(dp[i][j] < dp[i-1][j])
                    {
                        dp[i][j] = dp[i-1][j];
                        fa[i][j] = j;
                    }
                    if(dp[i][j+num[i]] < dp[i-1][j] + 1)
                    {
                        dp[i][j + num[i]] = dp[i-1][j] + 1;
                        fa[i][j + num[i]] = j;
                    }
                    if(dp[i][j - num[i]] < dp[i-1][j] + 1)
                    {
                        dp[i][j - num[i]] = dp[i-1][j] + 1;
                        fa[i][j - num[i]] = j;
                    }
                }
                l-=num[i];
                r+=num[i];
            }
            printf("%d\n", dp[n][30000]);
            int t = 30000;
            for(int i = n; i >= 1; i -- )
            {
                int tmp = fa[i][t];
                if(t > tmp) one.push_back(t - tmp);
                if(t < tmp) two.push_back(tmp - t);
                t = tmp;
            }
            int x, y;
            x = 0;
            y = 0;
            for(int i = 0; i < two.size(); i++)
            {
                y++;
                printf("%d %d\n", x, y);
                x += two[i];
                printf("%d %d\n", x, y);
            }
            y = 0;
            for(int i = 0; i < one.size(); i++)
            {
                y--;
                printf("%d %d\n", x, y);
                x -= one[i];
                printf("%d %d\n", x, y);
            }
            one.clear();
            two.clear();
        }
        return 0;
    }

分析：分析发现，就是给你一堆数，然后让你尽可能挑出多的数，分成两部分的和相等，我们可以用dp来解决这个问题。

[acdream 1429 Rectangular Polygon]: http://acdream.info/problem?pid=1429