• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            雪竹的天空
            
				
            theorix
            
			            		
		
            
	
            

            

            
	
            
		
            
			
 
C++博客 ::
首頁 ::
新隨筆 ::
聯系 ::
聚合
 ::
管理 ::


			
			
				

            
	
            
		
            
			
			
			
				 
				34 
				隨筆 ::
				0 文章
				::
				20 評論
				::
				0 Trackbacks
			
		
            
	
            

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		簡單的dp題
            注意輸出函數的編寫
            還有dp方程
            

              1/****************************************************************
              2    Problem: 1171
              3    User: theorix
              4    Language: C++
              5    Result: Accepted
              6    Time:152 ms
              7    Memory:980 kb
              8****************************************************************/
              9
             10#include<iostream>
             11#include<math.h>
             12using namespace std;
             13#define NN 5000
             14int ans[NN+9];
             15int mem[NN+9][2];
             16int xans[NN+9];
             17int xmem[NN+9][2];
             18int chose[NN+9];
             19void output2(int n)
             20{
             21    if(xmem[n][0]==0)
             22    {
             23        int i;
             24        for(i=1;i<=n;i++)
             25            printf("|");
             26        return ;
             27    }
             28    output2(xmem[n][0]);
             29    printf("x");
             30    output2(xmem[n][1]);
             31}
             32void output(int n)
             33{
             34    if(chose[n]==0)
             35    {
             36        for(int i=1;i<=n;i++)
             37            printf("|");
             38    }
             39    else if(chose[n]==1)
             40    {
             41        output(mem[n][0]);
             42        printf("+");
             43        output(mem[n][1]);
             44    }
             45    else if(chose[n]==2)
             46    {
             47        output2(mem[n][0]);
             48        printf("x");
             49        output2(mem[n][1]);
             50    }
             51}
             52int main()
             53{
             54//    freopen("toothpicks.in","r",stdin);
             55//    freopen("out.txt","w",stdout);
             56    int i,j,k,n,t,tt;
             57    xans[1]=1;
             58    for(i=2;i<=NN;i++)
             59    {
             60        t=(int)sqrt(i);
             61        xans[i]=i;
             62        for(j=2;j<=t;j++)
             63        {
             64            if(i%j==0&&xans[j]+xans[i/j]+2<xans[i])
             65            {
             66                xans[i]=xans[j]+xans[i/j]+2;
             67                xmem[i][0]=j;
             68                xmem[i][1]=i/j;
             69            }
             70        }
             71    }
             72    ans[1]=1;
             73    chose[1]=0;
             74    for(i=2;i<=NN;i++)
             75    {
             76        t=(int)sqrt(i);
             77        ans[i]=i;
             78        chose[i]=0;
             79        for(j=1;j<=i/2;j++)
             80        {
             81            if(ans[j]+ans[i-j]+2<ans[i])
             82            {
             83                ans[i]=ans[j]+ans[i-j]+2;
             84                mem[i][0]=j;
             85                mem[i][1]=i-j;
             86                chose[i]=1;
             87            }
             88        }
             89        for(j=2;j<=t;j++)
             90        {
             91            if(i%j==0&&xans[j]+xans[i/j]+2<=ans[i])
             92            {
             93                ans[i]=xans[j]+xans[i/j]+2;
             94                mem[i][0]=j;
             95                mem[i][1]=i/j;
             96                chose[i]=2;
             97            }
             98        }
             99    }
            100//for(i=1;i<=160;i++)cout<<i<<" "<<chose[i]<<endl;
            101//    for(n=1;n<=NN;n++)
            102    while(scanf("%d",&n)!=EOF)
            103    {//printf("%d\n",n);
            104        printf("%d toothpicks: ",ans[n]);
            105        output(n);
            106        printf("=%d\n",n);
            107    }
            108}
            109
            

	
            
	
	
            
		posted on 2008-09-06 21:04 雪竹的天空( theorix ) 閱讀(506) 評論(0)  編輯 收藏 引用  所屬分類: 解題報告 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



久久亚洲国产精品五月天婷|
久久精品国产只有精品2020|
欧美色综合久久久久久|
久久93精品国产91久久综合|
久久夜色撩人精品国产小说|
99久久国产精品免费一区二区|
狠狠色丁香久久婷婷综合蜜芽五月|
久久精品国产99久久久古代
|
久久久久久久久久久免费精品|
久久精品中文字幕第23页|
久久强奷乱码老熟女网站
|
午夜精品久久久久久久无码|
亚洲欧美成人久久综合中文网
|
三级片免费观看久久|
亚洲国产精品无码久久SM|
91久久九九无码成人网站|
一本色道久久综合狠狠躁篇|
久久国产精品成人免费|
精品久久亚洲中文无码|
精品熟女少妇aⅴ免费久久|
久久精品国产亚洲AV香蕉|
久久久人妻精品无码一区|
久久人人爽人人爽人人AV东京热
|
久久99精品久久只有精品
|
久久久这里有精品|
久久精品国产亚洲Aⅴ香蕉|
久久精品中文闷骚内射|
7777精品伊人久久久大香线蕉
|
久久精品aⅴ无码中文字字幕不卡
久久精品aⅴ无码中文字字幕重口
|
亚洲愉拍99热成人精品热久久|
久久精品国产亚洲AV不卡|
青青青伊人色综合久久|
久久精品亚洲一区二区三区浴池
|
国产精品岛国久久久久|
国产激情久久久久久熟女老人|
久久久无码精品亚洲日韩软件|
国产免费久久久久久无码|
久久精品国产99国产电影网|
国产精品无码久久综合|
精品久久久久久无码专区不卡|
久久亚洲精品人成综合网|