| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
一开始递推公式写错了,悲剧,代码好丑#include <stdio.h>
#include <limits.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)>(b)?(b):(a))
int label[100];
char letter[100];
struct
{
int min;
int max;
}dp[50][100];
int op(int x,int y, char c)
{
switch(c)
{
case 't': return x+y;
case 'x': return x*y;
}
}
int main()
{
int n,i,j,k,n1,n2,n3,n4;
scanf ("%d", &n);
for (i = 0; i < n; i++)
{
getchar();
scanf ("%c %d", &letter[i], &label[i]);
letter[i+n] = letter[i];
label[i+n] = label[i];
}
for (i = 0; i < n; i++)
for (j = 0; j < n*2; j++)
{
dp[i][j].max = INT_MIN;
dp[i][j].min = INT_MAX;
}
for (i = 0; i < n; i++)
dp[0][i].max = dp[0][i].min = dp[0][i+n].max = dp[0][i+n].min= label[i];
for (i = 1; i < n; i++)
for (j = 0; j < n; j++)
for (k = 0; k < i; k++)
{
n1 = op(dp[k][j].max,dp[i-k-1][j+k+1].max,letter[j+k+1]);
n2 = op(dp[k][j].max,dp[i-k-1][j+k+1].min,letter[j+k+1]);
n3 = op(dp[k][j].min,dp[i-k-1][j+k+1].max,letter[j+k+1]);
n4 = op(dp[k][j].min,dp[i-k-1][j+k+1].min,letter[j+k+1]);
if (dp[i][j].max < MAX(MAX(n1,n2),MAX(n3,n4)))
dp[i][j].max = dp[i][j+n].max = MAX(MAX(n1,n2),MAX(n3,n4));
if (dp[i][j].min > MIN(MIN(n1,n2),MIN(n3,n4)))
dp[i][j].min = dp[i][j+n].min = MIN(MIN(n1,n2),MIN(n3,n4));
}
j = INT_MIN;
for (i = 0; i < n; i++)
{
if (dp[n-1][i].max > j)
j = dp[n-1][i].max;
}
printf ("%d\n", j);
for (i = 0; i < n; i++)
{
if (dp[n-1][i].max == j)
printf ("%d ", i+1);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator