The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

POJ 1179 多边形游戏 区间动规

实际上就是枚举所有区间,求出所有区间可以获得的最大值和最小值,区间L的的结果可以由区间L-1的结果组合得到。
这题有一个小技巧很好用,就是求第i个结点顺时针向后的第t个结点如果是node(i,t)的话,那么node (i,t+1)的标号可以由
((i+t)%n )+1得到,实际上lebel[node(i,t)]=((i+t-1)%n )+1;所以这题结点从1开始存似乎更加便于计算。
//coded by abilitytao
//2010年6月1日17:25:38
#include <iostream>
#include
<algorithm>
#include
<cmath>
using namespace std;
const int maxn=100;

int n;
int fmax[maxn][maxn];
int fmin[maxn][maxn];
int v[maxn];
int op[maxn];
void init()//初始化
{

    
for(int i=1;i<=n;i++)
        
for(int j=1;j<=n;j++)
        
{
            fmax[i][j]
=-999999999;
            fmin[i][j]
=999999999;
        }

        
for(int i=1;i<=n;i++)
            fmax[i][
0]=fmin[i][0]=v[i];
}


void input()
{

    scanf(
"%d",&n);
    cin.ignore();
    
int i;
    
for(i=1;i<=n;i++)
    
{
        
char tem[10];
        scanf(
"%s",tem);
        
if(tem[0]=='t')
            op[i]
=0;//0代表+号
        else
            op[i]
=1;//1代表乘号
        scanf("%d",&v[i]);
    }

}



void solve()//DP过程
{
    
int mm=-999999999;
    
int i,t,L;
    
for(L=1;L<=n-1;L++)
    
{
        
for(i=1;i<=n;i++)
        
{
            
for(t=0;t<=L-1;t++)
            
{

                
if(op[(i+t)%n+1]==0)
                
{
                    fmin[i][L]
=min(fmin[i][L],fmin[i][t]+fmin[(i+t)%n+1][L-t-1]);
                    fmax[i][L]
=max(fmax[i][L],fmax[i][t]+fmax[(i+t)%n+1][L-t-1]);
                }

                
else
                
{
                    fmin[i][L]
=min(fmin[i][L],fmin[i][t]*fmin[(i+t)%n+1][L-t-1]);
                    fmin[i][L]
=min(fmin[i][L],fmin[i][t]*fmax[(i+t)%n+1][L-t-1]);
                    fmin[i][L]
=min(fmin[i][L],fmax[i][t]*fmin[(i+t)%n+1][L-t-1]);
                    fmin[i][L]
=min(fmin[i][L],fmax[i][t]*fmax[(i+t)%n+1][L-t-1]);

                    fmax[i][L]
=max(fmax[i][L],fmin[i][t]*fmin[(i+t)%n+1][L-t-1]);
                    fmax[i][L]
=max(fmax[i][L],fmin[i][t]*fmax[(i+t)%n+1][L-t-1]);
                    fmax[i][L]
=max(fmax[i][L],fmax[i][t]*fmin[(i+t)%n+1][L-t-1]);
                    fmax[i][L]
=max(fmax[i][L],fmax[i][t]*fmax[(i+t)%n+1][L-t-1]);
                }

            }

        }

    }

    
for(i=1;i<=n;i++)
        
if(fmax[i][n-1]>mm)
            mm
=fmax[i][n-1];
    printf(
"%d\n",mm);
    
for(i=1;i<=n;i++)
        
if(fmax[i][n-1]==mm)
            printf(
"%d ",i);
    printf(
"\n");
}


int main()
{
    input();
    init();
    solve();
    
return 0;
}

posted on 2010-06-01 17:26 abilitytao 阅读(2063) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理