分别枚举矩形的上下边,把问题转化为求一维的最大子段。
#include<iostream>
using namespace std;
int arr[105][105];
int n,t[105];
const int inf=100000000;
int maxsubr()
{
int maxn=-inf,sum=0;
for(int i=1;i<=n;i++)
{
if(sum>0)
sum+=t[i];
else
sum=t[i];
if(maxn<sum)
maxn=sum;
}
return maxn;
}
int main()
{
int i,j;
int ans=-inf;
scanf("%d",&n);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&arr[i][j]);
for(i=1;i<=n;i++)
{
memset(t,0,sizeof(t));
for(j=i;j<=n;j++)
{
for(int k=1;k<=n;k++)
{
t[k]+=arr[j][k];
}
int temp=maxsubr();
if(ans<temp) ans=temp;
}
}
printf("%d\n",ans);
return 0;
}
posted @
2010-08-11 10:19 wuxu 阅读(115) |
评论 (0) |
编辑 收藏
枚举+贪心
把每钓5分钟鱼称为钓一次鱼。首先枚举John需要走过的池塘的数目X,即从池塘1走到池塘X。减去路上花去的时间T=sum(Ti) i=1...X-1,这样我们可以认为John能从一个池塘"瞬间转移"到另一个池塘,即在任意一个时刻都可以在池塘1到池塘X中任选一个钓一次鱼(很重要)。现在采用贪心策略,每次选择鱼最多的池塘钓一次鱼。对于每个池塘来说,由于在任何时候鱼的数目只和John在该池塘里钓鱼的次数有关,和钓鱼的总次数无关,所以这个策略是最优的。假设一共允许钓k次鱼,那么每次在N个池塘中选择鱼最多的一个钓。总的时间复杂度为O(kn^2)。 在最后的结果中,第一个最大值所对应的在每个池塘的钓鱼时间为题目要求的情况,因为如果John在后面的池塘钓了鱼,那么前面相应的时间就会减少。最后注意池塘中没有鱼的情况。
#include<iostream>
using namespace std;
int n,h,ans;
int f[26],t[26],d[26];
int main()
{
int i,k,total,j=0;
int fish[26],time[26],tt[26];
while(scanf("%d",&n)!=EOF&&n)
{
scanf("%d",&h);
h*=12;
for(i=1;i<=n;i++) scanf("%d",&f[i]);
for(i=1;i<=n;i++) scanf("%d",&d[i]);
t[1]=0;
for(i=2;i<=n;i++)
{
scanf("%d",&t[i]);
t[i]+=t[i-1];
}
ans=-1;
for(i=1;i<=n;i++)
{
total=0;
int remain=h-t[i];
memcpy(fish,f,sizeof(f));
memset(tt,0,sizeof(tt));
while(remain>0)
{
int maxn=-1,cur=-1;
for(k=1;k<=i;k++)
{
if(fish[k]>maxn)
{
maxn=fish[k];
cur=k;
}
}
total+=maxn;
fish[cur]-=d[cur];
if(fish[cur]<0) fish[cur]=0;
tt[cur]+=5;
remain--;
}
if(total>ans)
{
ans=total;
memcpy(time,tt,sizeof(tt));
}
}
if(j) printf("\n");
j=1;
for(i=1;i<=n;i++)
{
if(i==n) printf("%d \n",time[i]);
else printf("%d, ",time[i]);
}
printf("Number of fish expected: %d\n",ans);
}
return 0;
}
posted @
2010-08-10 20:13 wuxu 阅读(239) |
评论 (0) |
编辑 收藏
摘要: 刚学编程的时候写的,留下来做个纪念。一、初步设计1、新建工程slidwindow,在MFC的向导第一步选择Single Document,按Finish结束。2、选择ResourceView窗口,打开菜单编辑器,在顶层菜单上添加“开始”和“单步”菜单,其ID分别为ID_START_SLIDWIND和ID_TRACE_SLIDWIND,在 &...
阅读全文
posted @
2010-08-10 00:20 wuxu 阅读(1424) |
评论 (0) |
编辑 收藏
做该题的时候,看了网上另外一个版本的递推关系,不过还是朴素一点的比较好理解.状态转移方程为:
f[i,j]=max{f[i-1,j-1],f[i-1,j],f[i-1,j+1]}+w(i,j), 其中f[i,j]表示第i 秒 ,门开放度为j 时的最大加分.w(i,j)表示在该状态下的所有加分.为防止超内存用滚动数组.(由于不仔细把1写成了i,调试了半天,杯具了~~) 详细见代码:
#include<iostream>
#include<algorithm>
using namespace std;
int f[2][102];
int hash[30002];
int N,K,T,ans;
typedef struct
{
int t,p,s;
}Gant;
Gant s[102];
int cmp(Gant a,Gant b)
{
if(a.t<b.t) return 1;
else if(a.t==b.t)
{
if(a.s<b.s) return 1;
}
return 0;
}
int main()
{
int i,j,k;
scanf("%d%d%d",&N,&K,&T);
for(i=1;i<=N;i++) scanf("%d",&s[i].t);
for(i=1;i<=N;i++) scanf("%d",&s[i].p);
for(i=1;i<=N;i++) scanf("%d",&s[i].s);
memset(hash,0,sizeof(hash));
memset(f,-1,sizeof(f));
for(i=1;i<=N;i++) hash[s[i].t]=1;
sort(s+1,s+N+1,cmp);
f[0][0]=0;
ans=0;
for(i=1;i<=T;i++)
for(j=0;j<=K;j++)
{
int w=0;
if(hash[i])
{
for(k=1;k<=N;k++)
if(s[k].t==i&&s[k].s==j)
w+=s[k].p;
}
if(j>=1&&f[(i-1)&1][j-1]!=-1&&f[i&1][j]<f[(i-1)&1][j-1]+w)
f[i&1][j]=f[(i-1)&1][j-1]+w;
if(j+1<=K&&f[(i-1)&1][j+1]!=-1&&f[i&1][j]<f[(i-1)&1][j+1]+w)
f[i&1][j]=f[(i-1)&1][j+1]+w;
if(f[(i-1)&1][j]!=-1&&f[i&1][j]<f[(i-1)&1][j]+w)
f[i&1][j]=f[(i-1)&1][j]+w;
if(ans<f[i&1][j]) ans=f[i&1][j];
}
printf("%d\n",ans);
return 0;
}
posted @
2010-08-09 17:43 wuxu 阅读(133) |
评论 (0) |
编辑 收藏
一道很经典的DP,状态转移方程为:f[i,j,k]=max{f[i-1,j,k],f[i-1,j-1,k-(p[i]-d[i])]+p[i]+d[i]}。其中f[i,j,k]表示在前i个候选人中选择j个人,并且辩控差为k时的最大辩控和。另外用path[i,j,k]来记录路径,表示当前方案下选择的最后一个人。详细见代码:
#include<iostream>
#include<stack>
using namespace std;
int n,m,test;
int p[205],d[205];
int f[205][25][805];
int path[205][25][805];
int main()
{
test=0;
while(scanf("%d%d",&n,&m)!=EOF&&(m||n))
{
int i,j,k;
for(i=1;i<=n;i++)
scanf("%d%d",&p[i],&d[i]);
int mid=m*20;
memset(f,-1,sizeof(f));
memset(path,-1,sizeof(path));
for(i=0;i<=n;i++) f[i][0][mid]=0;
for(i=1;i<=n;i++)
for(j=1;j<=m&&j<=i;j++)
for(k=0;k<=2*mid;k++)
{
f[i][j][k]=f[i-1][j][k];
path[i][j][k]=path[i-1][j][k];
if(k>=p[i]-d[i]&&k-(p[i]-d[i])<=2*mid
&&f[i-1][j-1][k-(p[i]-d[i])]!=-1
&&f[i][j][k]<=f[i-1][j-1][k-(p[i]-d[i])]+p[i]+d[i])
{
f[i][j][k]=f[i-1][j-1][k-(p[i]-d[i])]+p[i]+d[i];
path[i][j][k]=i;
}
}
i=0;
int conc;
while(i<=mid)
{
if(f[n][m][mid+i]!=-1||f[n][m][mid-i]!=-1)
break;
i++;
}
if(f[n][m][mid+i]>f[n][m][mid-i])
conc=mid+i;
else conc=mid-i;
int prose=0,def=0;
stack<int> ss;
i=path[n][m][conc];
j=m;
while(i!=-1)
{
prose+=p[i];
def+=d[i];
ss.push(i);
j=j-1;
conc-=(p[i]-d[i]);
i=path[i-1][j][conc];
}
printf("Jury #%d\n",++test);
printf("Best jury has value %d for prosecution and value %d for defence:\n",prose,def);
while(!ss.empty())
{
printf(" %d",ss.top());
ss.pop();
}
printf("\n\n");
}
return 0;
}
posted @
2010-08-09 01:16 wuxu 阅读(238) |
评论 (0) |
编辑 收藏
首先建一个虚结点,权值为无穷大. 将入度为0的点与之相连, 然后做树形DP,为了防止重复,父亲单独考虑.详细见代码:
#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<sstream>
using namespace std;
const int inf=1000000000;
vector<int> G[210];
int dp[210][210];
int cost[210],in_degree[210];
bool vis[210];
int n,m;
int min(int a,int b)
{
return a<b?a:b;
}
int dfs(int u)
{
int i,j,k,v;
int num=1;
vis[u]=1;
dp[u][0]=0;
for(i=0;i<G[u].size();i++)
{
v=G[u][i];
if(vis[v]) continue;
num+=dfs(v);
}
for(i=0;i<G[u].size();i++)
{
v=G[u][i];
for(j=n;j>=0;j--)
for(k=1;k<=n;k++)
{
if(j>=k&&dp[u][j]!=-1&&dp[u][j-k]!=-1&&dp[v][k]!=-1)
dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[v][k]);
else if(j>=k&&dp[u][j]==-1&&dp[u][j-k]!=-1&&dp[v][k]!=-1)
dp[u][j]=dp[u][j-k]+dp[v][k];
}
}
if(dp[u][num]!=-1&&dp[u][num]>cost[u])
dp[u][num]=cost[u];
else if(dp[u][num]==-1) dp[u][num]=cost[u];
return num;
}
int main()
{
int i,j;
char str[1000];
while(gets(str))
{
if(str[0]=='#') break;
sscanf(str,"%d%d",&n,&m);
for(i=0;i<=n;i++) G[i].clear();
map<string,int>graph;
memset(in_degree,0,sizeof(in_degree));
int id=0;
for(i=1;i<=n;i++)
{
scanf("%s",str);
if(graph.find(str)==graph.end()) graph[str]=++id;
int u=graph[str];
scanf("%d",&cost[u]);
gets(str);
stringstream ss(str);
string name;
while(ss>>name)
{
if(graph.find(name)==graph.end()) graph[name]=++id;
G[u].push_back(graph[name]);
in_degree[graph[name]]++;
}
}
cost[0]=inf;
for(i=1;i<=n;i++)
{
if(in_degree[i]) continue;
G[0].push_back(i);
}
memset(vis,0,sizeof(vis));
memset(dp,-1,sizeof(dp));
dfs(0);
int ans=inf;
for(j=m;j<=n;j++)
if(dp[0][j]!=-1&&dp[0][j]<ans)
ans=dp[0][j];
printf("%d\n",ans);
}
//system("pause");
return 0;
}
posted @
2010-08-07 15:03 wuxu 阅读(129) |
评论 (0) |
编辑 收藏
摘要: 树形背包。代码如下:
#include<iostream>#include<vector>using namespace std;int n,m;int num[105],brain[105];int dp[105][105];int vis[105];vector<int> map[105...
阅读全文
posted @
2010-08-07 01:25 wuxu 阅读(1326) |
评论 (0) |
编辑 收藏
依赖背包(树形背包)。见代码:
#include<iostream>
#include<vector>
using namespace std;
int N,M;
int val[205];
int vis[205];
int f[205][205];
int dp[205][205];
vector<int> tree[205];
int max(int a,int b)
{
return a>b?a:b;
}
void dfs(int x)
{
int i,j,k;
vis[x]=1;
dp[x][0]=0;
f[x][0]=0;
for(i=0;i<tree[x].size();i++)
for(j=M;j>=0;j--)
{
int temp=tree[x][i];
if(!vis[temp]) dfs(temp);
for(k=0;k<=M;k++)
{
if(dp[temp][k]!=-1&&j>=k&&f[x][j-k]!=-1)
f[x][j]=max(f[x][j],f[x][j-k]+dp[temp][k]);
}
}
for(i=1;i<=M+1;i++)
if(f[x][i-1]!=-1) dp[x][i]=f[x][i-1]+val[x];
}
int main()
{
while(scanf("%d%d",&N,&M)!=EOF&&(N||M))
{
int i,a,b;
for(i=0;i<=N;i++)
tree[i].clear();
for(i=1;i<=N;i++)
{
scanf("%d%d",&a,&b);
tree[a].push_back(i);
val[i]=b;
}
val[0]=0;
memset(vis,0,sizeof(vis));
memset(dp,-1,sizeof(dp));
memset(f,-1,sizeof(f));
dfs(0);
printf("%d\n",dp[0][M+1]);
}
return 0;
}
posted @
2010-08-05 18:00 wuxu 阅读(951) |
评论 (4) |
编辑 收藏