URAL 1495. One-two, One-two 2

dp[ i ][ j ] 表示 长度为 i 的 对 n 取余为 j (若 j == 0 , j = n) 的最优解。

mod[1][ i ] 表示1 * (10)^(i-1) 对 n 取余的余数，若 (mod[1][ i ] == 0 ,则 mod[ 1 ][ i ] = n)。mod[2][ i ]同理。

状态转移方程 dp[ i ][ j ] = min(dp[ i-1 ][j - mod[1][ i- 1]] + 1*(10)^(i-1) , dp[ i-1 ][j - mod[2][ i- 1]] + 2*(10)^(i-1) )。

状态转移方程很像背包，但是若按背包那样去求解，最坏的时间复杂度会到 30*100W。应该会TLE，我没有去试。。

但是如果从 长度为 i 的状态 推出 长度为 i+1 的状态，即用BFS的方式从前往后推，时间复杂度很降低很多，但是依然TLE了。

原因在于无法确定推出的状态是否为最优解,因为 dp[i+1][ j ] 会从dp[ i ][ k ]推出多种方案。使得许多无用的状态都被计算了一次。

好吧，现在已经找到了剪枝的关键点，即剪掉这些无用的状态。

acc[ i ][ j ] 记录已经出现的解中最优的一个。从而使得加入BFS队列中的方案越来越靠近最优解，即最后一个加入队列的关于 dp[ i ][ j ]的解即为此种状态下的最优解。

还有一个问题就是最终的答案的值可能是个大数，但是因为只有1 和 2 ，所以可以用二进制来解决。

另外，int 的 30*100W的数组貌似会超内存，所以注意用滚动数组优化。

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>

#pragma comment(linker, "/STACK:1024000000");
#define EPS (1e-6)
#define LL long long int
#define ULL unsigned long long int
#define _LL __int64
#define _INF 0x3f3f3f3f
#define INF 40000000
#define Mod 1000000007

using namespace std;

int mod[3][33];

struct N
{
    int ans,num;
} acc[2][1000010];

int ans[2][1000010];

struct Q
{
    int ans,num,acc;
};

void Output(int n,int ans)
{
    int temp = acc[ans%2][n].num;

    int num[31],top = 0;

    while(ans >= 1)
    {
        num[top++] = temp%2;
        temp /= 2;
        ans--;
    }

    for(top--; top >= 0; top--)
    {
        printf("%d",num[top]+1);
    }
    puts("");

}

void bfs(int n)
{
    memset(acc,0,sizeof(acc));
    memset(ans,0,sizeof(ans));

    queue<Q> q;

    Q f,t;

    f.acc = mod[2][1];
    f.ans = 1;
    f.num = 1;

    q.push(f);

    ans[1][mod[2][1]]++;
    acc[1][mod[2][1]].ans = 1;
    acc[1][mod[2][1]].num = 1;

    f.acc = mod[1][1];
    f.ans = 1;
    f.num = 0;

    q.push(f);

    ans[1][mod[1][1]]++;
    acc[1][mod[1][1]].ans = 1;
    acc[1][mod[1][1]].num = 0;

    while(q.empty() == false)
    {
        f = q.front();
        q.pop();

        if(ans[f.ans%2][f.acc] != 1)
        {
            ans[f.ans%2][f.acc]--;
        }
        else
        {

            ans[f.ans%2][f.acc] = 0;

            if(f.acc == n)
            {
                Output(n,f.ans);
                return ;
            }

            if(f.ans < 30 && acc[f.ans%2][f.acc].num == f.num )
            {
                t.ans = f.ans+1;
                t.acc = (f.acc + mod[1][t.ans])%n;
                t.acc = (t.acc == 0 ? n : t.acc);

                t.num = f.num;

                if(acc[t.ans%2][t.acc].ans != t.ans || t.num < acc[t.ans%2][t.acc].num)
                {
                    acc[t.ans%2][t.acc].ans = t.ans;
                    acc[t.ans%2][t.acc].num = t.num;
                    ans[t.ans%2][t.acc]++;
                    q.push(t);
                }

                t.ans = f.ans+1;
                t.acc = (f.acc + mod[2][t.ans])%n;
                t.acc = (t.acc == 0 ? n : t.acc);
                t.num = f.num + (1<<(f.ans));

                if(acc[t.ans%2][t.acc].ans != t.ans || t.num < acc[t.ans%2][t.acc].num)
                {
                    acc[t.ans%2][t.acc].ans = t.ans;
                    acc[t.ans%2][t.acc].num = t.num;
                    ans[t.ans%2][t.acc]++;
                    q.push(t);
                }
            }
        }
    }
    printf("Impossible\n");
}

int main()
{
    int n,i;

    scanf("%d",&n);

    if(n%10 == 5 || n%10 == 0)
    {
        printf("Impossible\n");
        return 0;
    }

    mod[1][1] = 1%n;
    mod[1][1] = (mod[1][1] == 0 ? n : mod[1][1]);

    mod[2][1] = 2%n;
    mod[2][1] = (mod[2][1] == 0 ? n : mod[2][1]);

    for(i = 2; i <= 30; ++i)
    {
        mod[1][i] = (mod[1][i-1]*10)%n;
        mod[1][i] = (mod[1][i] == 0 ? n : mod[1][i]);

        mod[2][i] = (mod[2][i-1]*10)%n;
        mod[2][i] = (mod[2][i] == 0 ? n : mod[2][i]);
    }

    bfs(n);

    return 0;
}

URAL 1495. One-two, One-two 2,布布扣,bubuko.com

URAL 1495. One-two, One-two 2

原文：http://blog.csdn.net/zmx354/article/details/21452007