51 条题解

  • 6
    @ 2018-05-14 22:09:46

    实在不会做看了各路大佬分享的题解,希望我记住了这种递推!

    f = [0, 0, 2, 4, 12]
    n = int(input())
    for i in range(5, n+1):
        f.append(2*f[i-1]+2*f[i-2]-2*f[i-3]+f[i-4])
    
    print(f[n])
    
  • 5
    @ 2023-08-23 14:36:04
    /*****************
    备注:
    *****************/
    #include <iostream>
    #include <iomanip>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    #include <cstdio>
    #include <set>
    #include <queue>
    #include <bitset>
    #include <deque>
    #include <stack>
    #include <ctime>
    using namespace std;
    #define LL long long
    #define MAXM 3010
    #define MAXN 3010
    const int N =1e5+10;
    const int INF =0x3f3f3f3f;
    int a[11],h,cnt=0; 
    int main ()
    {
        
        for(int i=1;i<=10;i++)
        {
            cin>>a[i];
        }
        cin>>h;
        for(int i=1;i<=10;i++)
        {
            if(a[i]<=h+30)
            {
                cnt++;
            }
        }
            
        cout<<cnt;  
       return 0;
    }
    
  • 2
    @ 2015-01-25 11:19:24

    #include<cstdio>
    using namespace std;
    struct arr{int n,p[1001];}g[1001],f[1001];
    int n,i;
    arr chen(arr a)
    {
    for (int i=1;i<=a.n;i++)
    a.p[i]*=2;
    for (int i=1;i<=a.n;i++)
    if (a.p[i]>9) {a.p[i+1]+=a.p[i]/10;a.p[i]%=10;}
    if (a.p[a.n+1]>0) a.n++;
    return a;
    }
    arr add(arr a,arr b)
    {
    a.n=a.n>b.n?a.n:b.n;
    for (int i=1;i<=a.n;i++)
    a.p[i]+=b.p[i];
    for (int i=1;i<=a.n;i++)
    if (a.p[i]>9) {a.p[i+1]+=a.p[i]/10;a.p[i]%=10;}
    if (a.p[a.n+1]>0) a.n++;
    return a;
    }
    arr Minus(arr a,arr b)
    {
    int i=1,j,k;
    while (i<=b.n)
    {
    if (a.p[i]>=b.p[i])a.p[i]=a.p[i]-b.p[i];
    else
    {
    j=i+1;
    while (a.p[j]==0) j++;
    a.p[j]--;
    for (k=i+1;k<j;k++) a.p[k]=9;
    a.p[i]=a.p[i]+10-b.p[i];
    }
    i++;
    }
    while (a.p[a.n]==0&&a.n>1)a.n--;
    return a;
    }
    int main()
    {
    //freopen("vans.in","r",stdin);
    //freopen("vans.out","w",stdout);
    scanf("%d",&n);
    g[1].p[1]=2;g[2].p[1]=2;g[3].p[1]=8;
    g[1].n=g[2].n=g[3].n=1;
    f[1].p[1]=0;f[2].p[1]=2;f[3].p[1]=4;
    f[1].n=f[2].n=f[3].n=1;
    for (i=4;i<=n;i++)
    {
    g[i]=Minus(add(chen(f[i-1]),add(g[i-1],g[i-2])),g[i-3]);
    f[i]=add(f[i-1],g[i-1]);
    }
    for (i=f[n].n;i>0;i--)
    printf("%d",f[n].p[i]);
    printf("\n");
    }

  • 1
    @ 2008-08-31 20:16:32

    (转载自http://billylinux.blog.hexun.com/10542440_d.html,感谢作者!)

    这一题可以用DP解决:

    考虑到要经过每一个点,那么对于最后形成的路,每一竖条横向的路不是4条就是2条,总共8种(不考虑路径方向):

    1 2 3 4 5 6 7 8

    - - - - -

    - - - - -

    - - - - -

    - - - - -

    (7中最上面的与最下面的相连、8中最上面的与第二个相连)

    并且对于经过最后面的4个点,路径形状只可能是两种(3、8),于是我们定义两个状态

    a[i]——有i竖条,以3号形状结尾的路径数

    b[i]——有i竖条,以8号形状结尾的路径数

    例如:对于i=3:

    a[3]=2 b[3]=2

    接下来的问题,就是如何进行状态转移:

    我们考虑下面的几种情况:

    对于a[i],它可以接在a、a……与b、b……上(这里的接上,指的是中间不出现3号与8号路径),并且除了a以外,其他都有两种接法(a有3种),因此经过分类,我们可以得到:

    a[i]=2*(a+a+……+a[2]+b+b+……+b[2]+1)+a

    而对于b[i],不难发现,他只能接在a与b上,因此有

    b[i]=a+b

    于是我们可以将a[i]化简为

    a[i]=a+2+2*(b+b+……b[3])

    至此问题大致解决,另外需要注意的是要用高精度。

    推荐使用亿进制。

  • 1
    @ 2008-08-30 07:43:43

    很巧妙的dp题。。。很难想,但超好编,枚举每列横向边的情况即可

    注意 要高精度

  • 0
    @ 2019-03-25 23:33:36

    1000位大整数魔鬼,可别说我耍赖皮,没有内存限制,吃掉了快5MB才AC
    ```cpp
    #include <iostream>

    using namespace std;

    int l[1001][1000]={0};
    //{0,0,2,4,12,0}
    //l[i]=l[i-4]-l[i-3]*2+l[i-2]*2+l[i-1]*2
    void outl(int n)
    {
    int i;
    bool flag=false;
    for(i=0;i<1000;i++)
    {
    if(l[n][i]!=0)
    {
    flag=true;
    }
    if(flag)
    {
    cout<<l[n][i];
    }
    }
    //cout<<endl;
    }

    void add(int n)
    {
    int i,temp;
    for(i=0;i<1000;i++)
    {
    l[n][i]=l[n-4][i]-(l[n-3][i]*2)+(l[n-2][i]*2)+(l[n-1][i]*2);
    }
    for(i=999;i>0;i--)
    {

    if(l[n][i]>=10)
    {
    temp=l[n][i]/10;
    l[n][i]=l[n][i]%10;
    l[n][i-1]+=temp;
    }

    /*
    while(l[n][i]>10)
    {
    l[n][i]-=10;
    l[n][i-1]++;
    }
    */
    while(l[n][i]<0)
    {
    l[n][i]+=10;
    l[n][i-1]--;
    }
    }
    }

    int main()
    {
    l[0][999]=0;
    l[1][999]=0;
    l[2][999]=2;
    l[3][999]=4;
    l[4][999]=2;
    l[4][998]=1;
    int n,i;
    cin>>n;
    if(n>4)
    {
    for(i=5;i<=n;i++)
    {
    add(i);
    }
    }
    outl(n);
    return 0;
    }

  • 0
    @ 2018-02-13 23:26:03

    解题思路:

    1)参考:http://www.docin.com/p-94253938.html

    2)注意:递归的性能优化

    3)注意:大整数的处理
    可参考:http://blog.csdn.net/loophome/article/details/79322682

  • 0
    @ 2017-03-31 14:19:58
    #include <vector>
    #include <iostream>
    #include <cmath>
    #include <cstring>
    using namespace std;
    struct BigInt
    {
        static const int Base = 100000000;
        static const int Width = 8;
        vector <int> s;
        BigInt (long long num = 0) 
        {
            *this = num;
        }
        BigInt operator = (long long num)
        {
            s.clear();
            do
            {
                s.push_back(num % Base);
                num /= Base;
            }while (num > 0);
            return *this;
        }
        BigInt operator + (const BigInt &b) const
        {
            BigInt res;
            res.s.clear();
            for (int i = 0, count = 0;;i++)
            {
                if (count == 0 && i >= s.size() && i >= b.s.size()) break;
                int x = count;
                if (i < s.size()) x += s[i];
                if (i < b.s.size()) x += b.s[i];
                res.s.push_back(x % Base);
                count = x / Base;
            }
            return res;
        }
        
        BigInt operator - (const BigInt &b) const
        {
            BigInt res;
            res.s.clear();
            for (int i = 0, carry = 0;;i++)
            {
                if (carry == 0 && i >= s.size() && i >= b.s.size()) break;
                int x = carry;
                carry = 0;
                if (i < s.size()) x += s[i]; else break;
                if (i < b.s.size()) x -= b.s[i];
                if (x < 0) 
                {
                    carry = -1;
                    x += Base;
                }
                res.s.push_back(x %Base);
            }
            return res;
        }
        friend  ostream& operator << (ostream &out, const BigInt& x)
        {
            out << x.s.back();
            for(int i = x.s.size()-2; i >= 0; i--)
            {
                char buf[20];
                sprintf(buf, "%08d", x.s[i]);
                for(int j = 0; j < strlen(buf); j++) out << buf[j];
            }
            return out;
        }
    };
    
    int main()
    {
        int n;
        scanf("%d",&n);
        BigInt f[4]={0,0,1,2},g[4]={0,1,1,4};
        if (n < 4) cout << f[n] + f[n];
        else
        {
            for (int i = 4; i <=n; i++)
            {
                f[i%4] = f[(i-1)%4] + g[(i-1)%4];
                g[i%4] = f[(i-1)%4] + f[(i-1)%4] + g[(i-1)%4] +g[(i-2)%4] -g[(i-3)%4]; 
            }
            cout << f[n%4] + f[n%4];
        } 
        
        
    }
    
  • 0
    @ 2016-09-08 21:41:54

    递推式......太难了
    #include <cstdio>
    #include <cstring>

    int n,f[1100][300]={{0},{1,0},{1,2},{1,4},{1,12}};

    void addx(int a[],int b[]){
    int c[300]={0};
    int len=a[0]>b[0]?a[0]:b[0];
    for(int i=1;i<=len;i++){
    c[i]+=a[i]+b[i];
    c[i+1]+=c[i]/10000;
    c[i]%=10000;
    }
    len++;
    while(c[len]==0&&len>1)
    len--;
    c[0]=len;
    memcpy(a,c,sizeof(c));
    }

    void minusx(int a[],int b[]){
    int c[300]={0};
    int len=a[0];
    for(int i=1;i<=len;i++){
    c[i]+=a[i]-b[i];
    if(c[i]<0){
    c[i]+=10000;
    c[i+1]-=1;
    }
    }
    while(c[len]==0&&len>1)
    len--;
    c[0]=len;
    memcpy(a,c,sizeof(c));
    }

    void Q(int a[]){
    printf("%d",a[a[0]]);
    for(int i=a[0]-1;i>=1;i--)
    printf("%04d",a[i]);
    }

    int main(){
    freopen("plan.in","r",stdin);
    freopen("plan.out","w",stdout);
    scanf("%d",&n);
    if(n<=4){
    printf("%d",f[n][1]);
    return 0;
    }
    int t[300];
    for(int i=5;i<=n;i++){
    memcpy(f[i],f[i-4],sizeof(t));
    addx(f[i],f[i-2]);
    addx(f[i],f[i-2]);
    addx(f[i],f[i-1]);
    addx(f[i],f[i-1]);
    minusx(f[i],f[i-3]);
    minusx(f[i],f[i-3]);
    }
    Q(f[n]);
    return 0;
    }

  • 0
    @ 2016-06-06 15:56:19

    原题[不是本题]的题解(2):

    Program vans;
    function cf(x,y:integer):qword;
    var i:integer;
    begin
    cf:=1; for i:=1 to y do cf:=cf*x;
    end;
    var n,m:integer;
    begin
    assign(input,'vans.in'); reset(input);
    assign(output,'vans.out'); rewrite(output);
    readln(n,m); if n=2 then writeln(2)
    else writeln(cf(2,m div 2)); close(input); close(output);
    end.

  • 0
    @ 2016-06-06 15:55:59

    原题[不是本题]的题解(1):

    Program vans;//搜索
    const dx:array[1..4] of integer=(-1,0,1,0);
    dy:array[1..4] of integer=(0,-1,0,1);
    type arr=array[1..1000,1..1000] of boolean;
    procedure search( var a:arr; var n,m:integer; x,y,sum:integer; var all:integer; var ans:int64 );
    var i,u,v:integer;
    begin
    if sum=all then
    begin
    if (x=1)and(y=2) or (x=2)and(y=1) then
    ans:=ans+1;
    exit;
    end;
    for i:=1 to 4 do
    begin
    u:=x+dx[i]; v:=y+dy[i];
    if (0<u)and(u<=n)and(0<v)and(v<=m)and(a[u,v]=false) then
    begin
    a[u,v]:=true;
    search(a,n,m,u,v,sum+1,all,ans);
    a[u,v]:=false;
    end;
    end;
    end;
    var n,m,all,sum:integer;
    ans:int64;
    a:arr;
    begin
    assign(input,'vans.in'); reset(input);
    assign(output,'vans.out'); rewrite(output);
    readln(n,m);
    all:=n*m; sum:=1; a[1,1]:=true;
    search(a,n,m,1,1,1,all,ans);
    writeln(ans);
    close(input); close(output);
    end.

  • 0
    @ 2009-10-24 15:00:29

    递推+高精度

    递推式:

    f[1]:=0; f[2]:=2; f[3]:=4; f[4]:=12; (n=5)

    还有个就是: 诡异算法 by Maigo

    详细见nocow http://www.nocow.cn/index.php/USACO/vans

    • @ 2014-05-27 22:39:44

      怎么求得的递推式?

  • 0
    @ 2009-09-03 19:40:53

    将路径所围成的图形涂黑

    把状态表示成一列中方格的颜色(状态共6种,1表示黑色,0表示白色)(竖着看!)

    1 1 1 1 0 0

    1 0 0 0 0 1

    1 1 1 0 1 0

    其中第二种的两个方格在之前没有连通,第三种是连通的

    其余三种状态是不会出现的

    0 1 0

    1 1 0

    1 0 0

    方程大家可以自己想,而且我们只需要保存两列状态

  • 0
    @ 2008-11-10 10:38:35

    (楼上的楼上,我自己推的!)

    可能没化简,但是便于理解。数组的1.2.3.4.5都有很明显的意义。

    这里不会贴图,讲不清,到我空间上看吧。

    http://dfs35123.spaces.live.com/blog/cns!A6CB032EC0980F16!483.entry

    f[2,1]:=1;

    f[2,2]:=1;

    for i:=3 to n do

    begin

    f:=f+f+f+f;

    f:=f+f+f;

    f:=f+f;

    f:=f;

    f:=f+f;

    end;

    writeln(2*(f[n,1]+f[n,3]));

    用高精度!!

  • 0
    @ 2008-10-21 18:43:27

    很强大的推导……总算看懂了公式是怎么推导出来的了8个情况的分析……按照列来分层只有7 和 8两种情况能出现在最后的那一层

  • 0
    @ 2008-10-04 18:25:22

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    f[1]=0;f[2]:=2;f[3]:=4;f[4]:=12;(N=1,2,3,4)

    f[n]:=f[n-4]-f[n-3]*2+f[n-2]*2+f[n-1]*2;(N>=5)

    纯粹靠高精度啦。。。公式推导还算容易,大家看下面的就行了。。。

    突然发现高精度加减法用COMP压18位还不如longint压8位快。。。(>_

    • @ 2014-07-06 20:49:22

      ”公式推导还算容易“神犇

    • @ 2017-11-10 20:20:22

  • 0
    @ 2008-09-28 08:44:36

    参考了 Maigo 诡异的算法!!

    设a[i]表示第i列的左上和左下角有直线连通时的路径数,b[i]表示第i列的左上和左下角没有直线连通时的路径数,则有: b[i]:=a+b; a[i]=2+a+2(a+b+a+b+...) =2+a+2(b+b+...) 其中a[i]的值可以在计算过程中累加·!

    0MS通过!

    还有,加上高精度!

  • -1
    @ 2016-07-17 08:56:19

    USACO Chapter 6.1

  • -1
    @ 2016-03-04 17:09:41
    
    import java.math.BigInteger;
    import java.util.Scanner;
    
    public class Main {
    
        public static void main(String[] args) {
            BigInteger f[] = new BigInteger[1001];
            BigInteger g[] = new BigInteger[1001];
            final BigInteger _2 = BigInteger.valueOf(2);
            f[0] = f[1] = g[0] = BigInteger.ZERO;
            f[2] = g[1] = g[2] = BigInteger.ONE;
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            for (int i = 3; i <= n; ++i) {
                f[i] = f[i - 1].add(g[i - 1]);
                g[i] = f[i - 1].multiply(_2).add(g[i - 1]).add(g[i - 2]).subtract(g[i - 3]);
            }
            System.out.println(f[n].multiply(_2));
        }
    
    }
    
    
  • -1
    @ 2009-07-30 12:09:24

    状态压缩+递推. 算是从另一个角度解释了 fammiebright的 题解吧,一个思路-_-||有比较详细的分析,题解:

信息

ID
1435
难度
5
分类
动态规划 | 状态压缩DP递推 点击显示
标签
(无)
递交数
1209
已通过
433
通过率
36%
被复制
6
上传者