惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

T
Tenable Blog
Last Week in AI
Last Week in AI
P
Proofpoint News Feed
Engineering at Meta
Engineering at Meta
H
Help Net Security
F
Fortinet All Blogs
MyScale Blog
MyScale Blog
宝玉的分享
宝玉的分享
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
博客园 - 司徒正美
量子位
N
Netflix TechBlog - Medium
Apple Machine Learning Research
Apple Machine Learning Research
小众软件
小众软件
Recorded Future
Recorded Future
博客园 - 三生石上(FineUI控件)
Vercel News
Vercel News
aimingoo的专栏
aimingoo的专栏
I
InfoQ
Microsoft Security Blog
Microsoft Security Blog
Scott Helme
Scott Helme
The Last Watchdog
The Last Watchdog
cs.AI updates on arXiv.org
cs.AI updates on arXiv.org
IT之家
IT之家
AI
AI
WordPress大学
WordPress大学
Security Archives - TechRepublic
Security Archives - TechRepublic
Google Online Security Blog
Google Online Security Blog
U
Unit 42
V2EX - 技术
V2EX - 技术
MongoDB | Blog
MongoDB | Blog
Schneier on Security
Schneier on Security
博客园 - Franky
H
Heimdal Security Blog
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
Jina AI
Jina AI
W
WeLiveSecurity
P
Privacy & Cybersecurity Law Blog
Cloudbric
Cloudbric
B
Blog RSS Feed
N
News | PayPal Newsroom
S
Securelist
Threat Intelligence Blog | Flashpoint
Threat Intelligence Blog | Flashpoint
I
Intezer
Hacker News - Newest:
Hacker News - Newest: "LLM"
CTFtime.org: upcoming CTF events
CTFtime.org: upcoming CTF events
博客园_首页
罗磊的独立博客
H
Hackread – Cybersecurity News, Data Breaches, AI and More
雷峰网
雷峰网

博客园 - xmx

Amazon 2面杯具 N皇后回溯 "中航文化杯" 2007 ACM/ICPC 国际大学生程序设计竞赛亚洲区域赛(南京) 一个用来练dfs的简单迷宫问题 pku 1662 还是找规律的 pku 1806 Manhattan 2025(找规律) 今天西华的比赛,啥都不说啦,相当的nice!~~~ 今天北京赛区的比赛 最近看的一些东西 The 2007 ACM Asia Programming Contest Changchun Site Internet Preliminary Contest nice 位运算果真是好东西,今天算是学到点啦^_^ FOJ月赛-2007年9月 pku 1850 前面一直没注意到某个不规范的情况,导致结果一直比标准的大...调了好久... 终于有算最长重复子串(数)的后缀数组啦,nice The 2007 ACM Asia Programming Contest - Nanjing Preliminary pku 3219 人家居然用几十B就过了,肯定有超强的规律,可是我自己找了个,挂了...只能老实算... 一道双向dp,差点超时^_^||| dp pku 1050 N和素数P,求杨辉三角第N行中能被P整除的数的个数
pku 1505 copying books(DP)
xmx · 2007-10-10 · via 博客园 - xmx

#include<stdio.h>
#include<string>
#include<algorithm>
using namespace std;

int t,k,m;
int books[510];
int dp[510][510];
int part[510];

#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))

int sum(int i,int j)
{
 int t=0,p;
 for(p=i;p<=j;p++)
  t += books[p];
 return t;
}

void cal2()
{
 int i,j,l,st;
 for(i=1;i<=k;i++)
  dp[i][1] = sum(i,k);

 dp[k][1] = books[k];

 for(i=2;i<=m;i++)
 {
  dp[k-i+1][i] = Max(books[k-i+1], dp[k-i+2][i-1]);
  j = k-i+1;
  for(l=k-i; l>=m-i+1; l--)
  {
   if(sum(l,j) <= dp[j+1][i-1])
    dp[l][i] = dp[j+1][i-1];
   else if(books[l] >= dp[l+1][i-1])
    dp[l][i] = books[l] , j = l;
   else
   {
    while(sum(l,j-1) >= dp[j][i-1])
     j--;
    dp[l][i] = Min( sum(l,j), dp[j][i-1]);
    if(dp[l][i] == dp[j][l-1])
     j--;
   }
  }
 }
}

int main()
{
 int i ,j, st;
 
 scanf("%d",&t);
 books[0]=0;
 while(t--)
 {
  scanf("%d %d",&k,&m);
  for(i=1;i<=k;i++) scanf("%d",&books[i]);
  memset(dp,0,sizeof(dp));
  cal2();

  st = 0; j = 0;
  for(i=k;i>=1;i--)
  {
   st += books[i];
   if(st > dp[1][m])
   {
    part[j++] = i+1;
    st = books[i];
   }
     if(st == dp[1][m])
   {
    if(m-j <= i)
    {
     part[j++] = i;
     st = 0;
    }
    else
    {
     part[j++] = i+1;
     st = books[i];
    }
   }
  }

  j--;
  printf("%d",books[1]);
  for(i=k;i<=2;i++)
  {
   if(i == part[j])
   {
    printf(" /");
    j--;
   }
   printf(" %d",books[i]);
  }
  printf("\n");
 }
}