?? 最大連續和的最小值.txt
字號:
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define CISHUMAX 105
#define SHITOUMAX 100005
#define MAX 9999999
int f[SHITOUMAX][CISHUMAX];
int weight[SHITOUMAX];
//最大連續和的最小值 PKU 3273 Monthly Expense
//此題用動態規劃會超時,但作為一種方法,不妨記錄下來
/*
輸入:
8 3
1 2 3 4 5 6 7 8
*/
void cal(int num,int duan)
{
int i,j,temp,max,k;
for(i=1;i<=num;i++)
f[i][1]=f[i-1][1]+weight[i];
// print(num,duan);
for(j=2;j<=duan;j++)
{ //分成j塊
for(i=j;i<=num;i++)
{ //當前石頭個數為i
temp=MAX;
for(k=1;k<i;k++)
{ //k+1,...,i為新塊數的石頭
if(f[i][1]-f[k][1]<f[k][j-1]) max=f[k][j-1];
else max=f[i][1]-f[k][1];
if(max<temp) temp=max;
}
f[i][j]=temp;
// print(num,duan);
}
}
}
int main()
{
int num,duan,i;
scanf("%d%d",&num,&duan);
for(i=1;i<=num;i++)
scanf("%d",&weight[i]);
cal(num,duan);
cout<<f[num][duan]<<endl;
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -